Mother Vertex

Problem Overview

A mother vertex in a directed graph is one from which all other vertices are reachable.

Intuition

A mother vertex in a directed graph is one from which all other vertices are reachable. A key insight: if a mother vertex exists, it will always be the last vertex to finish in a DFS traversal (due to the structure of the graph). So we find the last-finished vertex, then verify it by checking if all vertices are reachable from it.

Algorithm

1Build the adjacency list from the edge list.
2Run DFS from each unvisited vertex, tracking the last vertex to finish�this is the candidate.
3Reset the visited array.
4Run DFS from the candidate vertex.
5If all vertices are visited, the candidate is the mother vertex; otherwise, return -1.

Example Walkthrough

Input: V = 4, edges = [[0,1],[0,2],[1,3],[2,3]]

1. Adjacency: 0?[1,2], 1?[3], 2?[3], 3?[].
2. DFS traversal: visit 0, then 1, then 3 (finished 3), backtrack, visit 2 (finished 2), backtrack (finished 1), backtrack (finished 0).
3. Last finished vertex: 0.
4. Verify: DFS from 0 reaches 1, 2, 3. All 4 vertices reachable.
5. Return 0 (the mother vertex).

Output: 0

Common Pitfalls

• Do not assume the first vertex with the highest out-degree is the mother; topology matters.
• The last-finished vertex in DFS is the candidate only because of the directed acyclic structure; in cyclic graphs, revisit the approach.
• After finding the candidate, always verify it; not all graphs have a mother vertex.

Mother Vertex.java

Java


import java.util.*;

// Approach: A mother vertex (if it exists) will be the last finished vertex in DFS traversal.
// First DFS pass: track all finished vertices, the last one is the candidate.
// Second DFS pass: verify the candidate by checking if all vertices are reachable from it.
// If verification succeeds, return the candidate; otherwise return -1.
// Time: O(V + E) Space: O(V)

class Solution {

    public int findMotherVertex(int V, int[][] edges) {
        // Step 1: Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
        }

        // Step 2: Do DFS to find candidate mother vertex
        boolean[] visited = new boolean[V];
        int candidate = -1;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                candidate = i; // last finished vertex
            }
        }

        // Step 3: Verify candidate by running DFS again
        Arrays.fill(visited, false);
        dfs(candidate, adj, visited);

        for (boolean v : visited) {
            if (!v) {
                return -1; // not all reachable

            }
        }

        return candidate;
    }

    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int nei : adj.get(node)) {
            if (!visited[nei]) {
                dfs(nei, adj, visited);
            }
        }
    }
}

Was this solution helpful?