Could not find the level of last node of the graph

Question

I want to print the level of each node. I could print the level of every node but the last node. Please help me to debug the code to find out why my code is not printing the level of the last node. For the below sample input/output it printed level of node 10 is 0 The actual level of node 10 is 4.

Graphical representation of the sample input graph is given below

input

10 14  
1 2  
1 4  
1 3  
2 6  
4 7 
3 7  
3 8  
6 10  
7 9  
8 5  
8 7  
9 10  
5 10  

My output

Level of 1 is :0  
Level of 2 is :1  
Level of 3 is :1  
Level of 4 is :1  
Level of 5 is :3  
Level of 6 is :2  
Level of 7 is :2  
Level of 8 is :2  
Level of 9 is :3  
Level of 10 is :0  

code

int main() {
    int N, E;
    scanf("%d%d", & N, & E);
    int level[N];
    for (int i = 0; i <= N; i++) {
        level[i] = -1;
    }
    for (int i = 1; i <= E; i++) {
        int x, y;
        scanf("%d%d", & x, & y);
        edges[x].push_back(y);
    }
    int source = 1;
    level[source] = 0;
    for (int i = source; i <= N; i++) {
        int l = edges[i].size();

        printf("Node %d is connected to: ", i);
        for (int j = 0; j < l; j++) {
            printf("%d ", edges[i][j]);
            if (level[edges[i][j]] == -1) {
                level[edges[i][j]] = level[i] + 1;
            }

        }
        printf("\n");
    }
    int size = sizeof(level) / sizeof(int);
    for (int i = 1; i <= size; i++) {
        printf("Level of %d is :%d\n", i, level[i]);
    }
    return 0;
}

I do not understand what I am missing here.

Answer 1

#include <stdlib.h>
#include <vector>
using namespace std;

#define MAX 100000

vector<int> edges[MAX];
vector<int> vis[MAX];

int main() {

    int numNodes, numEdges; // number of edges

    // reading number of nodes
    printf("Please input number of nodes: ");
    scanf("%d", &numNodes);
    // reading number of edges
    printf("Please input number of edges: ");
    scanf("%d", &numEdges);
    int level[numNodes];

    for (int i = 0; i < numNodes; i++) {
        level[i] = -1;
    }

    // reading edges
    printf("Please input the %d edges in the form of \"NODE1 NODE2\":\n", numEdges);
    for (int i = 0; i < numEdges; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[x-1].push_back(y);
        edges[y-1].push_back(x);
        printf("\nEdge #%d stored! Please input %d more edge(s).\n", i+1, 13-i-1);
    }

    level[0] = 0;

    // printing edges for all nodes
    for (int i = 0; i < numNodes; i++) {
        int l = edges[i].size();

        printf("Node %d is connected to: ", i+1);

        if (l == 0) {
            printf("nothing!\n", i+1);
            break;
        }
        for (int j = 0; j < l; j++)
        {
            printf("%d ", edges[i][j]);

        // update nodes' levels
        /* if the adjacent node's level is lower than the current node's level and the adjacent node node is the larger node,
        OR if the adjacent node's level is -1 (means it had not been updated yet),
        then the adjacent node's level should be changed to the current node's level + 1.
        This is possible because it implicitly appears that higher numbered nodes are given higher levels,
        e.g. when 1 is connected by an edge to 2, it is assumed that 2 is at level 1 and 2 is at level 0,
        rather than the other way around.*/
        if (((level[edges[i][j]-1] < level[i]) && (edges[i][j] > i+1)) || (level[edges[i][j]-1] == -1)) {
            level[edges[i][j]-1] = level[i] + 1;
            }
        }
        printf("\n");
    }

    // printing level of all nodes
    for(int i = 0; i < numNodes; i++) {
        printf("Level of node %d is: %d\n", i+1, level[i]);
    }

    return 0;
}

Some changes I have made:

1. Refactored the code to include better indentations, variable names and slight commentation.

2. Fixed the indexes used for the various loops. Your code would have asked scanned for 13 edges when you input that there were to be 14.

3. Made it bidirectional storage of edges so as to print all adjacent edges for each node.

4. Fixed the update process of the nodes' level.

5. Removed unnecessary variables.

6. Added additional console messages.