Level of Nodes

Problem Statement - link #

Given a Undirected Graph with V vertices and E edges, Find the level of node X. if X does not exist in the graph then print -1. Note: Traverse the graph starting from vertex 0.

Your Task: You dont need to read input or print anything. Your task is to complete the function nodeLevel() which takes two integers V and X denoting the number of vertices and the node, and another adjacency list adj as input parameters and returns the level of Node X. If node X isn’t present it returns -1.

Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:

X = 4
Output:
2
Explanation: 

We can clearly see that Node 4 lies at Level 2.

Constraints #

• 2 ≤ V ≤ 10^4
• 1 ≤ E ≤ (N*(N-1))/2
• 0 ≤ u, v ≤ V
• 1 ≤ w ≤ 10^4
• Graph doesn’t contain multiple edges and self loops.

Solutions #

class Solution
{
    public:
	//Function to find the level of node X.
	int nodeLevel(int V, vector<int> adj[], int X) 
	{
	    // code here
	    queue<pair<int,int>>q;
	    bool vis[V]={0};
	    vis[0]=1;
	    q.push({0,0});
	    while(!q.empty()){
	        auto u=q.front();
	        if(X==u.first)return u.second;
	        q.pop();
	        for(int i:adj[u.first]){
	            if(!vis[i]){
	                q.push({i,u.second+1});
	                vis[i]=true;
	            }
	        }
	    }
	    return -1;
	}
};