Level Of nodes-gfg

The today's POTD was somewhat related to yesterday one in terms of the approach that was required although I felt like tackling the previous one was quite confusing and much more challenging than this one.

Maybe that's bcz I got a fair idea of the depth of this logic from the yesters prob. 

Overall I just made a logical error while assuming that in whichever level I get the X vertex, that level will be the final answer, but I missed that we'll have to go another edge to finally get to the X vertex, but overall this problem took me somewhat 15 minutes, logical and coding part combined.

Although in the starting I was gonna go in a really drastic approach of confusing this with the level-order traversal of Binary Tree but the prob that would have arised with that is that this is a similar looking but yet completely different stuff, here I am not gonna get any functionality of just 2 child nodes... cause there are no nodes here, neither is there any boundations of how many neighbours a vertex can have.

Overall if someone is experienced with the adjacency list(not sure if I should even say an adj list, cause here they didn't even give the edges, but gave the neighbours, maybe a "NEIGHBOUR ADJ. MATRIX") provided in prob then it's only gonna be about the visualisation part and the concept of having a visited list just like the one in Prim's Algo.

Yeah, job done ;)

Trying to keep my codes as simple and self-explanatory, cause I need to work on the naming conventions as well as the code prettiness.

Because I was just focussing on the logic part so decided to go with python cause I didn't wanna complicate things unnecessarily with C++, that's just too much stupid syntax.

Problem Statement:-

Given an integer X and an undirected acyclic graph with V nodes, labeled from 0 to V-1, and E edges, find the level of node labeled as X.

Level is the minimum number of edges you must travel from the node 0 to some target.

If there doesn't exists such a node that is labeled as X, return -1.

Example 1:

Input:

X = 4
Output:
2Explanation:

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

Example 2:

Input:

X = 1
Output:
1
Explanation:
Node 1 lies at level 1, immediate after Node 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)
Expected Auxiliary Space: O(V)

Constraints:
2 ≤ V ≤ 104
1 ≤ E ≤ 104
0 ≤ adji, j < V
1 ≤ X < V
Graph doesn't contain multiple edges and self loops.

Code Implementation:-

class Solution:

    def __init__(self):

        self.ans=-1

       

    #Function to find the level of node X.

    def dfs(self,adj,visited,X,curr_vertex,curr_level):

       

        # Now this vertex is visited

        visited[curr_vertex]=1

       

        # exploring the vertices that we can go from this vertex

        # Here adj[curr_vertex] is a list which contains the negihbours

        # of the vertex curr_vertex

        for i in adj[curr_vertex]:

            if(i==X):

                # I am getting the desired vertex at the curr_level vertex,

                # means X is gonna be at the level curr_level+1

                self.ans=curr_level+1

                return True

           

            # If this vertex is not yet visited, then explore this, if returns true

            # then just return true, means we got the ans somewhere later

            if( visited[i]!=1 and self.dfs(adj,visited,X,i,curr_level+1) ):

                return True

               

            # if this vertex doesn't lead us to the desired X vertex then

            # I'll have to explore further vertices too

           

        # if there is no possible path from curr_vertex to X vertex, then

        # we are gonna be here and will return False

        return False

   

    def nodeLevel(self, V, adj, X):

        # code here

       

        # so that I don't take the ans of the previous Test Case

        self.ans=-1

       

        # To store which vertices are visited till now, if the vertex

        # is visited then its index will have 1 else -1

        visited=[-1 for i in range(V)]

       

        # Starting to go to the depth from the 0th vertex at 0 level

        self.dfs(adj,visited,X,0,0)

        return self.ans