Find a Mother Vertex in a Directed Graph

In a directed graph, a mother vertex is a vertex from which every other vertex can be reached by following edges. Return one mother vertex, or an empty OptionalInt if there isn't one. (OptionalInt holds either one int or nothing.) (If there are several, they can all reach each other, so any of them is a valid answer.)

Example 1

graph LR
    3 --> 0
    3 --> 1
    0 --> 1
    1 --> 2

Text

Output: 3   (3 reaches 0 and 1 directly, and 2 through 1)

Example 2

graph LR
    0 --> 1
    2 --> 1

Text

Output: empty   (0 and 2 can't reach each other)

A helper: mark everything reachable from a vertex

Both solutions use an iterative DFS that marks every vertex reachable from start. ArrayDeque is Java's array-backed double-ended queue, used here as a stack (push and pop work on the front). A vertex can be pushed more than once, but the visited check expands it only once.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Main {
    static void mark(List<List<Integer>> adj, int start, boolean[] visited) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                for (int w : adj.get(v)) {
                    stack.push(w);
                }
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1), List.of(2), List.of(), List.of(0, 1));
        boolean[] visited = new boolean[adj.size()];
        mark(adj, 3, visited);
        System.out.println(java.util.Arrays.toString(visited));
    }
}

Output

[true, true, true, true]

Brute force: try every vertex

For each vertex, run a DFS from it with fresh visited flags and check whether every vertex got marked.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static void mark(List<List<Integer>> adj, int start, boolean[] visited) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                for (int w : adj.get(v)) {
                    stack.push(w);
                }
            }
        }
    }

    static OptionalInt motherVertex(List<List<Integer>> adj) {
        for (int v = 0; v < adj.size(); v++) {
            boolean[] visited = new boolean[adj.size()];
            mark(adj, v, visited);
            boolean all = true;
            for (boolean seen : visited) {
                all &= seen;
            }
            if (all) {
                return OptionalInt.of(v);
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        List<List<Integer>> yes = List.of(List.of(1), List.of(2), List.of(), List.of(0, 1));
        List<List<Integer>> no = List.of(List.of(1), List.of(), List.of(1));
        System.out.println(motherVertex(yes) + " " + motherVertex(no));
    }
}

Output

OptionalInt[3] OptionalInt.empty

Time: O(V · (V + E)). Space: O(V).

Optimal: the root of the last DFS

Run DFS over the whole graph, sharing one visited array. Go through the vertices in order and start a new DFS from each vertex that hasn't been visited yet. Remember the vertex that started the last DFS. That vertex is the only possible mother vertex.

Why: suppose a mother vertex m exists.

If m starts its own DFS, that DFS reaches every vertex that's still unvisited, so no DFS can start after it, and m is the last root.
If m was already visited, some earlier root r reached it. Since r reaches m and m reaches everything, r reaches everything too, so again no later DFS starts. The last root is r, which is also a mother vertex.

Either way, the last root is a mother vertex, if one exists. It might not exist, so run one more DFS from the candidate to check.

Walkthrough with example 1 (0 → 1, 1 → 2, 3 → 0, 3 → 1):

vertex	visited?	action	visited after
0	no	DFS from 0 reaches 0, 1, 2; candidate = 0	{0, 1, 2}
1	yes	skip
2	yes	skip
3	no	DFS from 3 reaches 3; candidate = 3	{0, 1, 2, 3}

The candidate is 3. A fresh DFS from 3 reaches all four vertices, so 3 is a mother vertex.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static void mark(List<List<Integer>> adj, int start, boolean[] visited) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                for (int w : adj.get(v)) {
                    stack.push(w);
                }
            }
        }
    }

    static OptionalInt motherVertex(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        int candidate = -1;
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                mark(adj, v, visited);
                candidate = v;
            }
        }
        if (candidate == -1) {
            return OptionalInt.empty(); // empty graph
        }
        boolean[] check = new boolean[n];
        mark(adj, candidate, check);
        for (boolean seen : check) {
            if (!seen) return OptionalInt.empty();
        }
        return OptionalInt.of(candidate);
    }

    public static void main(String[] args) {
        List<List<Integer>> yes = List.of(List.of(1), List.of(2), List.of(), List.of(0, 1));
        List<List<Integer>> no = List.of(List.of(1), List.of(), List.of(1));
        List<List<Integer>> cycle = List.of(List.of(1), List.of(2), List.of(0)); // every vertex is a mother vertex
        System.out.println(motherVertex(yes) + " " + motherVertex(no) + " " + motherVertex(cycle));
        System.out.println(motherVertex(List.of()));
    }
}

Output

OptionalInt[3] OptionalInt.empty OptionalInt[0]
OptionalInt.empty

Time: O(V + E): two full traversals. Space: O(V).

The same argument, that the last vertex to finish in a full DFS belongs to a "source" part of the graph, is the first step of Kosaraju's algorithm for strongly connected components.

Edge cases

Empty graph: empty OptionalInt.
One vertex: it's the mother vertex.
A cycle through every vertex: every vertex is a mother vertex. The algorithm returns the last root, which is 0 here, since the first DFS reaches everything.