Mother Vertex

Given a Directed Graph, find a Mother Vertex in the Graph (if present).

Input: The first line of input contains an integer T. Then T test cases follow. Each test case contains two integers V (number of vertices) and E (number of edges). In the next line are E space separated values u,v denoting an edge from u to v. Output: For each testcase return the mother vertex of graph (if exists) else return -1.

Your Task: You don't need to read input or print anything. Your task is to complete the function findMother() which takes a Directed graph and the number of vertices as inputs and returns a Mother Vertex in the Graph. If the graph has mltiple Mother Vertices, return the one with the smallest value. If the Mother Vertex does not exist, return -1.

Expected Time Complexity: O(V + E). Expected Auxiliary Space: O(V).

Constraints: 1 <= T <= 500 1 <= V <= 500 1 <= E <= 3000 0 <= u, v < N

Example: Input: 2 5 5 1 0 0 2 2 1 0 3 3 4 3 2 0 1 2 1

Ouput: 0 -1

Explanation: Testcase 1: According to the given edges, all nodes can be reaced from nodes from 0, 1 and 2. But, since we are traversing from node 0, so 0 is the output.

Testcase 2: According to the given edges, no vertices are there from where we can reach all vertices. So, output is -1.

class MotherVertex {
    public static void fillStackDFS(int v, ArrayList<ArrayList<Integer>> graph, Stack<Integer> st, boolean[] visited) {
        visited[v] = true;
        for (int x : graph.get(v))
            if (!visited[x])
                fillStackDFS(x, graph, st, visited);
        st.push(v);
    }

    public static void fillStack(ArrayList<ArrayList<Integer>> graph, Stack<Integer> st) {
        boolean visited[] = new boolean[graph.size()];
        for (int i = 0; i < graph.size(); i++)
            if (!visited[i])
                fillStackDFS(i, graph, st, visited);
    }

    public static int countDFS(ArrayList<ArrayList<Integer>> graph, int sv, boolean[] visited) {
        int count = 1;
        visited[sv] = true;
        for (int x : graph.get(sv))
            if (!visited[x])
                count += countDFS(graph, x, visited);
        return count;
    }

    static int findMother(ArrayList<ArrayList<Integer>> graph, int n) {
        Stack<Integer> st = new Stack<>();
        fillStack(graph, st);
        // As we are doing DFS in sorted order of nodes (when filling stack)
        // then the mother vertex will be at top of stack (if mother vertex is present)
        int sv = st.pop();
        boolean visited[] = new boolean[graph.size()];
        int coveredNodes = countDFS(graph, sv, visited);
        if (coveredNodes == n)
            return sv;
        return -1;
    }
}