Road Constructor

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in company
Twitter

Problem statement

You are given an undirected graph with ‘N’ nodes and ‘M’ edges. Your task is to find out if it is possible to turn the graph into a directed graph such that all the vertices have positive in-degree.

Note: 
In-Degree of a vertex is the number of edges coming towards the node.
For example:

undirected

In the above graph, we can give direction to the first edge (0, 1), from vertex 0 to vertex 1 and the second edge (1, 2) from vertex 1 to vertex 2, and finally, the last edge (0, 2) from vertex 2 to vertex 0. So all nodes in-degree is 1. Hence the answer is “Yes”.

undirected

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, denoting the number of test cases.

The first line of each input contains two space-separated integers, ‘N’ and ‘M’, denoting the number of vertices and the number of edges, respectively.

The following ‘M’ lines of input contain two space-separated integers, ‘A’ and ‘B’, denoting a bidirectional edge between vertices ‘A’ and ‘B’.
Output Format: 
For each test case, If it is possible to make all vertices in-degree positive, then print “Yes”. Otherwise, print “No”.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
2 <= N <= 10^5
N - 1 <= M <= 10^5
0 <= A, B < N

Time Limit: 1 sec
Sample Input 1:
2
3 3
0 1
1 2
2 0
3 2
0 1
1 2
Sample Output 1:
Yes
No
Explanation:

undirected

For the first test case, we can give direction to the first edge (0, 1), from vertex 0 to vertex 1, and the second edge (1, 2) from vertex 1 to vertex 2, and the last edge (0, 2) from vertex 2 to vertex 0. So all nodes in-degree is 1. Hence the answer is “Yes”.

undirected

For the second test case, we can’t make all the vertices in degree positive. Hence the answer is “No”.
Sample Input 2:
2
4 3
0 1
2 1
2 3
4 4
0 1
1 2
2 0
2 1
Sample Output 2:
 No
 Yes
Hint

At which condition all nodes have positive in-degree.

Approaches (2)
Depth First Search

In this approach, we have to make the graph directed such that all nodes are reachable from every node. This can be done if a cycle is present in the graph so that all vertices can have at least one incoming edge. If there is even one cycle is present in the graph, every node is reachable, as other nodes will only have incoming edges. 

We define a dfs(graph, node, parent, visited) function that checks for a cycle in the graph and returns true or false. The graph is the adjacency list of the graph, the node is the current visiting node, the parent is the parent of the current node, and visited is a boolean array keeping track of the visited nodes.
 

Algorithm:

  • Make function dfs(graph, node, parent, visited), which returns true if a cycle is found in the graph. Otherwise, it returns False.
    • Check if the node is visited or not from the visited array. If the node is visited, we will return True.
    • Otherwise, make the current node visited by making visited[node] to True
    • Iterate through each neighbour of the node.
      • Check if the neighbour is equal to the parent, then move to the next node.
      • Otherwise, recursively call dfs function for the neighbour, and set the parent as the current node.
      • If dfs(graph, neighbour, node, visited) is true, we will return true from the function. Otherwise, continue iterating through the remaining neighbours.
    • If the function reaches the end, we will return false.
  • Make an adjacency list of list graph from the edges list.
  • Make a visited boolean array of length N and set every value to false.
  • Set result as dfs(graph, 0, -1, visited).
  • In the end, return the variable result.
Time Complexity

O(N + M), where N is the number of vertices of the graph and M is the number of edges.

 

The time complexity for doing a depth-first search on a graph is O(N + M). So the total time complexity becomes O(N + M).

Space Complexity

O(N + M), where N is the number of vertices of the graph and M is the number of edges.

 

In the worst case, the adjacency list requires O(N + M) space. The space complexity O(N) is required for maintaining a visited array of vertices and the recursion stack in the worst case. So the total space complexity becomes O(N + M + N) = O(N + M).

Code Solution
(100% EXP penalty)
Road Constructor
Full screen
Console