# Reorder Edges

Posted: 28 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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’

## 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.