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’

O(N), where ‘N’ is the total number of nodes in the graph.

We are using an adjacency list that takes O(N - 1) space as we need to insert ‘N’ - 1 edges into the list. Moreover, we need O(N) extra space in the form of recursive calls for depth-first search when the given graph is bamboo or a one-sided tree. 
Hence, the overall space complexity will be O(N) + O(N), which is O(N).

O(N), where ‘N’ is the total number of nodes in the graph.

Here, building the adjacency list will take O(N - 1) time since we have ‘N’ - 1 edges, and performing a depth-first search on the given graph takes O(N + N - 1) time. 

Hence, the overall time complexity will be O(N - 1) + O(2 * N - 1), which is O(N).

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is the total number of nodes in the graph.

*/



import java.util.ArrayList;



public class Solution 

{

    // This function is used to traverse the given graph and count the number of

    // non-reverse edges.

    public static int depthFirstSearch(int root, int parent, ArrayList> adjList) 

    {

        // To store the count of non-reverse edges

        int count = 0;



        // Run a loop for all the edges from 'root'

        for (int i = 0; i < adjList.get(root).size(); i++) 

        {

            int currNode = Math.abs(adjList.get(root).get(i));



            // If the current node is not the parent of 'root'

            if (currNode != parent) 

            {

                // Call the 'depthFirstSearch' funtion and add its returned value in 'count'

                count = count + depthFirstSearch(currNode, root, adjList);



                // If the  edge 'root' -> 'adjList[root][i]' if not a reverse edge

                if (adjList.get(root).get(i) > 0) 

                {

                    // Increment 'count' as we need to reverse it to make the path of the current node to node 0 valid.

                    count = count + 1;

                }

            }

        }



        return count;

    }



    public static int reorderEdges(int n, ArrayList> edgeList) 

    {

        ArrayList> adjList = new ArrayList<>(n);

        for(int i=0 ; i        {

            adjList.add(new ArrayList<>());

        }



        // Build adjacency list graph

        for (int i = 0; i < edgeList.size(); i++) 

        {

            int u = edgeList.get(i).get(0), v = edgeList.get(i).get(1);



            /*

                The given edge is u -> v

                So we will directly insert 'v' into the adjacency list of 'u'

            */

            adjList.get(u).add(v);



            /*

                We will add a reverse edge v -> u

                To mark this edge as a reverse edge we will insert -'u' into

                the adjacency list of 'v'

            */

            adjList.get(v).add(-1*u);

        }



        int answer = depthFirstSearch(0, -1, adjList);



        return answer;

    }

}

'''

    Time Complexity  :  O(N)

    Space Complexity :  O(N)



    where ‘N’ is the total number of nodes in the graph.

'''



# This function is used to traverse the given graph and count the number of non-reverse edges.

def depthFirstSearch(root, parent, adjList):



    # To store the count of non-reverse edges

    count = 0



    # Run a loop for all the edges from 'root'

    for i in range(len(adjList[root])):



        currNode = abs(adjList[root][i])



        # If the current node is not the parent of 'root'

        if (currNode != parent):



            # Call the 'depthFirstSearch' funtion and add its returned value in ‘count’

            count = count + depthFirstSearch(currNode, root, adjList)



            # If the  edge 'root' -> 'adjList[root][i]' if not a reverse edge

            if (adjList[root][i] > 0):



                # Increment 'count' as we need to reverse it to make the path of the current node to node 0 valid.

                count = count + 1

        

    return count



def reorderEdges(n, edgeList):



    adjList = [[] for i in range(n)]



    # Build adjacency list graph

    for i in range(len(edgeList)):

        u, v = edgeList[i][0], edgeList[i][1]



        '''

            The given edge is u -> v

            So we will directly insert 'v' into the adjacency list of 'u'

        '''

        adjList[u].append(v)



        '''

            We will add a reverse edge v -> u

            To mark this edge as a reverse edge we will insert -'u' into

            the adjacency list of 'v'

        '''

        adjList[v].append(-u)



    answer = depthFirstSearch(0, -1, adjList)



    return answer

/*
    Time Complexity  :   O(N)
    Space Complexity :   O(N)

    where ‘N’ is the total number of nodes in the graph.
*/

#include 

// This function is used to traverse the given graph and count the number of non-reverse edges.
int depthFirstSearch(int root, int parent, vector> &adjList) {

	// To store the count of non-reverse edges
	int count = 0;

	// Run a loop for all the edges from 'root'
	for (int i = 0; i < adjList[root].size(); i++) {

		int currNode = abs(adjList[root][i]);

		// If the current node is not the parent of 'root'
		if (currNode != parent) {

			// Call the 'depthFirstSearch' funtion and add its returned value in ‘count’
			count = count + depthFirstSearch(currNode, root, adjList);

			// If the  edge 'root' -> 'adjList[root][i]' if not a reverse edge
			if (adjList[root][i] > 0) {

				// Increment 'count' as we need to reverse it to make the path of the current node to node 0 valid.
				count = count + 1;
			}
		}
	}

	return count;
}

int reorderEdges(int n, vector> &edgeList) {

	vector> adjList(n);

	// Build adjacency list graph
	for (int i = 0; i < edgeList.size(); i++) {

		int u = edgeList[i][0], v = edgeList[i][1];

		/*
			The given edge is u -> v
			So we will directly insert 'v' into the adjacency list of 'u'
		*/
		adjList[u].push_back(v);

		/*
			We will add a reverse edge v -> u
			To mark this edge as a reverse edge we will insert -'u' into
			the adjacency list of 'v'
		*/
		adjList[v].push_back(-u);
	}

	int answer = depthFirstSearch(0, -1, adjList);

	return answer;
}

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’

O(N), where ‘N’ is the total number of nodes in the graph.

We are using an adjacency list that takes O(N - 1) space as we need to insert ‘N’ - 1 edges into the list, O(N) space is taken by ‘visited’ array to mark all ‘N’ nodes of the given graph, and O(N) space to store nodes in the queue during BFS, since when the given graph is a complete binary tree the last level of binary tree will have at least N / 2 nodes and in BFS we do level order traversal.
Hence, the overall space complexity will be O(N) + O(N) + O(N), which is O(N).

O(N), where ‘N’ is the total number of nodes in the graph.

Here, building the adjacency list will take O(N - 1) time since we have ‘N’ - 1 edges, and performing a breadth-first search on the given graph takes O(N + N - 1) time. 

Hence, the overall time complexity will be O(N - 1) + O(2 * N - 1), which is O(N).

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is the total number of nodes in the graph.

*/



import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;



public class Solution 

{

    public static int reorderEdges(int n, ArrayList> edgeList) 

    {

        ArrayList> adjList = new ArrayList<>(n);

        for(int i=0 ; i        {

            adjList.add(new ArrayList<>());

        }



        // Build adjacency list graph

        for (int i = 0; i < edgeList.size(); i++) 

        {

            int u = edgeList.get(i).get(0), v = edgeList.get(i).get(1);

    

            /*

                The given edge is u -> v

                So we will directly insert 'v' into the adjacency list of 'u'

            */

            adjList.get(u).add(v);

    

            /*

                We will add a reverse edge v -> u

                To mark this edge as a reverse edge we will insert -'u' into

                the adjacency list of 'v'

            */

            adjList.get(v).add(-1*u);

        }

    

        // To store the count of non-reverse edges

        int count = 0;

    

        Queue que = new LinkedList<>();

        boolean[] visited = new boolean[n];

        int currNode;

    

        // Insert node 0 in the queue and mark it as visited

        que.add(0);

        visited[0] = true;

    

        // Run a loop while the queue is not empty:

        while (que.isEmpty() == false) 

        {

            // Store the front element of the queue in 'currNode' and remove it from the queue

            currNode = que.peek();

            que.poll();

    

            // Run a loop for all the edges from 'root'

            for (int i = 0; i < adjList.get(currNode).size(); i++) 

            {

                int nextNode = Math.abs(adjList.get(currNode).get(i));

    

                // If 'nextNode' is not visited

                if (visited[nextNode] == false) 

                {

                    // mark 'nextNode' as visited

                    visited[nextNode] = true;



                    // If the  edge 'currNode' -> 'adjList[currNode][i]' if not a reverse edge

                    if (adjList.get(currNode).get(i) > 0) 

                    {

                        // Increment 'count'

                        count = count + 1;

                    }

    

                    // Insert 'nextNode' in the queue

                    que.add(nextNode);

                }

            }

        }

    

        return count;

	}

}

'''

    Time Complexity  :   O(N)

    Space Complexity :   O(N)



    where ‘N’ is the total number of nodes in the graph.

'''



from collections import deque



def reorderEdges(n, edgeList):



    adjList = [[] for i in range(n)]



    # Build adjacency list graph

    for i in range(len(edgeList)):

        u, v = edgeList[i][0], edgeList[i][1]



        '''

            The given edge is u -> v

            So we will directly insert 'v' into the adjacency list of 'u'

        '''

        adjList[u].append(v)



        '''

            We will add a reverse edge v -> u

            To mark this edge as a reverse edge we will insert -'u' into

            the adjacency list of 'v'

        '''

        adjList[v].append(-u)



    # To store the count of non-reverse edges

    count = 0

    que = deque()

    visited = [ False for i in range(n)]

    

    que.append(0)

    visited[0] = True



    # Run a loop while the queue is not empty:

    while que:



        # Store the front element of the queue in ‘currNode’ and remove it from the queue

        currNode = que.popleft()



        # Run a loop for all the edges from 'root'

        for i in range(len(adjList[currNode])):



            nextNode = abs(adjList[currNode][i])



            # If 'nextNode' is not visited

            if (visited[nextNode] == False):



                # mark 'nextNode' as visited

                visited[nextNode] = True



                # If the  edge 'currNode' -> 'adjList[currNode][i]' if not a reverse edge

                if (adjList[currNode][i] > 0):



                    # Increment 'count'

                    count = count + 1



                # Insert 'nextNode' in the queue

                que.append(nextNode)



    return count

/*
    Time Complexity  :   O(N)
    Space Complexity :   O(N)

    where ‘N’ is the total number of nodes in the graph.
*/

#include 
#include 

int reorderEdges(int n, vector> &edgeList) {

    vector> adjList(n);

    // Build adjacency list graph
    for (int i = 0; i < edgeList.size(); i++) {

        int u = edgeList[i][0], v = edgeList[i][1];

        /*
            The given edge is u -> v
            So we will directly insert 'v' into the adjacency list of 'u'
        */
        adjList[u].push_back(v);

        /*
            We will add a reverse edge v -> u
            To mark this edge as a reverse edge we will insert -'u' into
            the adjacency list of 'v'
        */
        adjList[v].push_back(-u);
    }

    // To store the count of non-reverse edges
    int count = 0;

    queue que;
    vector visited(n, false);
    int currNode;

    // Insert node 0 in the queue and mark it as visited
    que.push(0);
    visited[0] = true;

    // Run a loop while the queue is not empty:
    while (que.empty() == false) {

        // Store the front element of the queue in ‘currNode’ and remove it from the queue
        currNode = que.front();
        que.pop();

        // Run a loop for all the edges from 'root'
        for (int i = 0; i < adjList[currNode].size(); i++) {

            int nextNode = abs(adjList[currNode][i]);

            // If 'nextNode' is not visited
            if (visited[nextNode] == false) {

                // mark 'nextNode' as visited
                visited[nextNode] = true;

                // If the  edge 'currNode' -> 'adjList[currNode][i]' if not a reverse edge
                if (adjList[currNode][i] > 0) {

                    // Increment 'count'
                    count = count + 1;
                }

                // Insert 'nextNode' in the queue
                que.push(nextNode);
            }
        }
    }

    return count;
}