Reorder Edges

Posted: 28 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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’
Try Problem