Solution: Find a Mother Vertex in a Directed Graph

To identify a mother vertex in a directed graph, two primary methods can be employed. The first method utilizes depth-first search (DFS) from each vertex to determine if it can reach all other vertices, resulting in a time complexity of O(V(V + E)) and space complexity of O(V). The second method, based on Kosaraju’s algorithm, involves two phases: first identifying a candidate mother vertex through DFS, and then validating it by checking if all vertices are reachable from this candidate. This approach has a more efficient time complexity of O(V + E) and the same space complexity of O(V).