Distance to a Cycle in Undirected Graph

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in company
Intuit

Problem statement

You are given a graph with ‘N’ nodes and exactly one cycle. You are given a 2-d array ‘EDGES’, where ‘Edges[i]’=[‘node0’, ’node1’], denotes an undirected edge from node0 to node1. The nodes are numbered from 0 to ‘N’-1, where ‘N’ is the number of nodes in the graph.

The distance between two nodes is defined as the number of edges between them.

You must return an array ‘ANSWER’ of size ‘N’, where ‘ANSWER[i]’ is the shortest distance between node ‘i’ and any node present in the cycle.

Note :

The graph is connected.
There is, at most, one edge between any pair of nodes.
There is exactly one cycle in the graph.
Example:
Input: N=7, edges=[[1, 2], [2, 3], [3, 4], [4, 1], [0, 1], [5, 2], [6, 5]]

Output: [1, 0, 0, 0, 0, 1, 2]

Explanation: The Nodes 1, 2, 3, and 4 form a cycle.
The distance between nodes 0 to 1 is 1.
The distance between nodes 1 to 1 is 0.
The distance between nodes 2 to 2 is 0.
The distance between nodes 3 to 3 is 0.
The distance between nodes 4 to 4 is 0.
The distance between nodes 5 to 2 is 1.
The distance between nodes 6 to 2 is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format
First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains a single integer, ‘N,’ denoting the number of nodes in the graph.
The next ‘N’ lines contain two integers, ‘node0’ and ‘node1’, denoting an undirected edge between ‘node0’ and ‘node1’.
Output format:
Return the array ‘ANSWER’.
Note:-
You don't need to print anything. Just implement the given function.
Constraints :
1 <= 'T' <= 10
3 <= 'N' <= 10^5 
0 <= ‘node0’, ‘node1’ <=’N’-1
‘node0’ != ’node1’    

Time Limit: 1 sec
Sample Input 1 :
2
7
0 1
1 2
1 3
2 4
2 5
3 4
5 6
3
0 1
1 2
0 2
Sample Output 1 :
1 0 0 0 0 1 2
0 0 0 
Explanation Of Sample Input 1 :
For test case 1:

Input: N=7, edges=[[1, 2], [2, 3], [3, 4], [4, 1], [0, 1], [5, 2], [6, 5]]

Output: [1, 0, 0, 0, 0, 1, 2]

Explanation: The Nodes 1, 2, 3, and 4 form a cycle.
The distance between nodes 0 to 1 is 1.
The distance between nodes 1 to 1 is 0.
The distance between nodes 2 to 2 is 0.
The distance between nodes 3 to 3 is 0.
The distance between nodes 4 to 4 is 0.
The distance between nodes 5 to 2 is 1.
The distance between nodes 6 to 2 is 2.


For test case 2:

Input: N=3, edges=[[0, 1], [1, 2], [0, 2]]

Output: [0, 0, 0]

Explanation: The Nodes 0, 1, and 2 form a cycle.
The distance between nodes 0 to 0 is 0.
The distance between nodes 1 to 1 is 0.
The distance between nodes 2 to 2 is 0.
Sample Input 2 :
2
9
0 1 
1 2
0 2
2 6
6 7
6 8
1 3
3 4 
3 5 
4 
0 1
1 2
2 3
3 1    
Sample Output 2 :
0 0 0 1 2 2 1 2 2 
1 0 0 0 
Hint

The problem is a variation for finding the shortest distance between two points.

Approaches (1)
BFS

Approach:-
 

This problem can be solved in two steps. The first step is detecting a cycle, and the second is finding the distance for each node.

For the detecting cycle, we can remove leaf nodes and the associated edges. Any node with only one edge is known as a leaf node. All nodes left are part of the cycle.

For step two, push all the remaining nodes in a queue and start bfs to calculate the distance for all nodes.  

 

The steps are as follows:-

 

// Function to find the smallest path to a node present in a cycle.

        

    function smallestPath(int N, [int][int] edges):


 

  1. Initialize a 2-d array, ‘adjencyList’ of size ‘N’.
  2. For all edges in edges:
    • Push edge[1] in adjencyList[edge[0]]
    • Push edge[0] in adjencyList[edge[1]]
  3. Initialize an empty queue ‘leaves’.
  4. Initialize ‘adjCopy’ to ‘adjencyList’.
  5. For ‘i’ from 0 to ‘N’-1:
    • If adjCopy[i].size()==1:
      • leaves.push(i)
  6. While leaves.size():
    • Int leaf=leaves.top()
    • leaves.pop()
    • For all i in adjCopy[leaf]:
      • Erase ‘leaf’ from ‘adj[i]’.
      • If adjCopy[i].size()==1:
        • leaves.push(i)
    • adjCopy[ leaf ].clear()
  7. Initialize an empty queue ‘nodes’ and an integer variable ‘curDist’ equal to 0.
  8. Initialize an array ‘answer’ of size ‘N’ to -1.
  9. For ‘i’ from 0 to ‘N’-1:
    • If adjCopy[i].size()!=0:
      • nodes.push(i)
      • answer[i]=0
  10. While nodes.size()>0:
    • Int m = nodes.size()
    • For ‘i’ from 0 to m-1:
      • Int node = nodes.front()
      • nodes.pop()
      • For all j in adj[node]:
        • If answer[j] == -1:
          1. nodes.push(j)
          2. answer[j]=curDist+1
    • curDist++
  11. Return ‘answer’
Time Complexity

O( N ), where 'N' is the number of nodes in the graph.

 

We are doing a BFS traversal on the graph, which takes N+N time complexity, where N is the number of nodes and edges.

Space Complexity

O( N ), where 'N' is the number of nodes in the graph.

 

We are using a queue and an array of size ‘N’. Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Distance to a Cycle in Undirected Graph
Full screen
Console