Solution: Find a Mother Vertex in a Directed Graph

Let's solve the Find a Mother Vertex in a Directed Graph problem.

We'll cover the following

Statement

Given a directed graph as input, determine a mother vertex within it. A mother vertex in a graph G=(V,E)G = (V, E), is vertex VV such that all other vertices in GG can be reached by a path from VV. Although a graph might feature multiple mother vertices, your goal is to identify at least one.

Constraints:

  • 0≤0 \leq graph.length ≤104\leq 10^4

  • 0≤V,E≤1030 \leq V, E \leq 10^3

  • V≠EV \neq E

  • There are no repeated edges.

Solution 1: Depth-first search

To find a mother vertex in a given directed graph, we apply a depth-first search (DFS) strategy from each vertex to confirm if there’s a vertex from which all other vertices are reachable.We start by iteratively performing a depth-first search (DFS) starting from each vertex in the graph. For each vertex, we call perform_dfs() to see how many vertices can be reached from it. If the number of vertices reached from the current vertex is equal to the total number of vertices in the graph, it means that the current vertex can reach all other vertices and, thus, is a mother vertex. We return this vertex index. If no vertex meets the above condition, we return -1, indicating there’s no mother vertex in the graph.

We used a helper function, perform_dfs(), to perform a depth-first search starting from a source vertex and count how many vertices are reachable from this source. It initializes a list vertices_reached to keep track of visited vertices and a MyStack() stack to manage the DFS traversal. The source vertex is marked as visited and pushed onto the stack. While the stack is not empty, the algorithm continuously pops a vertex from the stack, and for each of its adjacent vertices:

  • If an adjacent vertex hasn’t been visited, it is marked as visited, pushed onto the stack, and the vertices_reached counter is incremented.

After traversing, the function returns the count of vertices reached plus one (to include the source vertex itself).

Now, let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.