Last Updated: 28 Mar, 2021
Reorder Edges
Moderate
Asked in companies
You are given a connected directed acyclic graph of ‘N’ nodes and ‘N’ - 1 edges, such that there is only one edge between any two nodes. You can perform the below operation on the given graph zero or more times:
1) Choose two nodes, ‘X’ and ‘Y’, such that there exists an edge between ‘X’ and ‘Y’.
2) Change the direction of this edge, i.e., if this edge is directed from ‘X’ to ‘Y’, change the direction of this edge to be directed from ‘Y’ to ‘X’ and vice versa.
Your task is to reorder the edges of the given graph in such a way that there exists a directed path from each node to node 0, using the minimum number of operations.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the total number of nodes in the given graph.
The next ‘N’ - 1 lines contains two space-separated integers, ‘U’ and ‘V’, where ‘U’ and ‘V’ represent the nodes that share a directed edge from ‘U’ to ‘V’.
Output Format :
For each test case, print the minimum number of operations required to make a directed path from each node to node 0.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 3000
0 <= U, V <= N - 1
Time Limit : 1sec
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The idea here is to convert the given directed acyclic graph into a bidirectional acyclic graph by adding reverse edges, i.e., for every edge present in the graph, we will add an edge with opposite direction.
For example:
Below, the left side directed graph will be converted into the right side undirected graph.
The edges marked in red are reverse edges.
Then we will do a depth-first search from node 0 and count the number of edges that are not reverse edges.
Algorithm:
- Declare a 2 - Dimensional array of integers, say ‘adjList’, to store the adjacency list of the given directed graph.
- Build the adjacency list using the edges array given in the problem.
- Call the ‘depthFirstSearch’ function with node 0 and ‘adjList’ as arguments, and store its returned value in ‘answer’
- Return ‘answer’
Description of ‘depthFirstSearch’ function
This function is used to traverse the given graph and count the number of non-reverse edges.
This function will take three parameters :
- root: An integer denoting the root node.
- parent: An integer denoting the parent node of the ‘root’ node.
- adjList: A 2 - Dimensional array of integers denoting the adjacency list of the given graph with reverse edges.
int depthFirstSearch(root, parent, adjList):
- Declare an integer ‘count’ to store the count of non-reverse edges.
- Run a loop for ‘i’ from 0 to the size of adjList[root] - 1
- Declare a integer say ‘currNode’ and initialize it with absolute value of ‘adjList[root][i]
- If ‘currNode’ is not equal to ‘parent’
- Call the ‘depthFirstSearch’ function with ‘currNode’, ‘root’, and ‘adjList’ as arguments, and add its returned value in ‘count’
- If the edge ‘root’ -> ‘adjList[root][i]’ is not a reverse edge:
- Increment ‘count’ i.e. do ‘count’ = count + 1 as we need to reverse it to make the path of the current node to node 0 valid.
- Return ‘count’
The idea is similar to the previous approach, but now we will do a breadth-first search from node 0 and count the number of non-reverse edges.
Algorithm:
- Declare a 2 - Dimensional array of integers, say ‘adjList’, to store the adjacency list of the given directed graph.
- Build the adjacency list using the edges array given in the problem.
- Declare an integer ‘count’ to store the count of non-reverse edges.
- Declare a queue of integers.
- Declare an array of booleans, say ‘visited’, to keep track of the visited nodes in breadth-first search.
- Declare an integer, say ‘currNode’, to keep track of the current node during our BFS traversal.
- Insert node 0 into the queue and mark this node as visited.
- Run a loop while the queue is not empty:
- Store the front element of the queue in ‘currNode’ and remove it from the queue.
- Run a loop for ‘i’ from 0 to the size of adjList[currNode] - 1:
- Declare a integer say ‘nextNode’ and initialize it with absolute value of ‘adjList[currNode][i]’
- If ‘nextNode’is not visited:
- Mark ‘nextNode’ as visited
- If the edge 'currNode' -> 'adjList[currNode][i]' if not a reverse edge:
- Increment ‘count’ i.e. do ‘count’ = count + 1 as we need to reverse it to make the path of the current node to node 0 valid.
- Insert ‘adjList[currNode][i]’ into the queue.
- Return ‘count’