Last Updated: 5 Dec, 2020
Road Constructor
Moderate
Asked in company
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:
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”.
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
Approaches
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.
As we have discussed in the previous approach, we are trying to find a cycle 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. In this approach, we will use a breadth-first search to find a cycle in the graph.
We define a bfs(graph, start, 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 start is the starting node, and visited is a boolean array keeping track of the visited nodes.
Algorithm:
- Make function bfs(graph, start, visited), which returns True if a cycle is found in the graph. Otherwise, it returns False.
- Initialize a queue q. Each queue element will be a tuple with the first element as the node and the second element as the node’s parent.
- Add the list of start and -1, in the queue.
- Make visited[start] equal to True
- While the queue is not empty
- Take out the front element of the queue. Set node equal to the front[0] and currentParent equal to the front[1].
- Iterate through all the neighbours of the node.
- If the neighbour equal to currentParent, skip this node.
- Check if the neighbour is visited, return True.
- Add neighbour and node(as the parent of neighbour) in the queue.
- If the function reaches the end, return false.
- Make an adjacency list of list graph from the edges list.
- Make a visited boolean array of length N and every value set to False.
- Set result as bfs(graph, 0, -1, visited).
- In the end, return the variable result.