Efficient approach
The efficient approach is based on the Idea of kosaraju's algorithm and strongly connected component. We will first find any mother vertex in the graph by optimizing the naive approach.
Mother vertices are always vertices of the source component in the component graph in a graph of strongly connected components. The concept is based on the following fact.
If a mother vertex (or vertices) exists, one of the mother vertices is the final vertex in DFS. (Or, in DFS traversal, a mother vertex has the fastest finish time.)
A recursive call for a vertex's DFS is considered to be ended in DFS if all descendants of the vertex have been visited.
Why this Idea works?
Let v be the last completed vertex. Essentially, we must show that an edge from another vertex u to v cannot exist if u is not another mother vertex (or that a non-mother vertex u cannot exist such that u-v is an edge). There are two possible outcomes.
- Before v, a recursive DFS call is done for u. Because v is reachable through u and a vertex finishes after all its children, if an edge u-v exists, v must have ended before u.
- Before u, a recursive DFS call is done for v. If an edge u-v exists in this instance as well, either v must complete before u (contrary to our assumption that v is finished at the end) OR u must be reachable from v. (which means u is another mother vertex).
If the mother vertex exists, then the vertices of the strongly linked component that contains the mother vertex are all mother vertices because if v is a mother vertex and there is a path from u->v, then u must be a mother vertex as well.
Steps of Algorithm
- Traverse the given graph using DFS. Keep track of the last completed vertex 'v' while traversing. This step takes O(V+E) seconds to complete.
- If a mother vertex (or vertices) exists, then v must be one of them (or one of them). DFS/BFS from v to see if it's a mother vertex. This phase requires O(V+E) time as well.
- Find the transpose of the graph, and store it in the new adjacency list to find the strongly connected components.
- Now call the DFS function on the mother vertex, and all other visited vertex through the mother vertex is also the mother vertices of the given graph because it is a strongly connected component with the mother vertex.
Implementation in C++
// recursive function to find the sum of depths of all subtree
#include<bits/stdc++.h>
using namespace std;
// calling the dfs function for every node
void dfs(int sv, vector<vector<int>>&adj, vector<bool>&vis){
vis[sv] = true;
for(auto it : adj[sv]){
if(!vis[it]) dfs(it, adj, vis);
}
return;
}
// checking if all the nodes are visited are not
void initializeVisited(vector<bool>&vis){
for(int i=0;i<vis.size();i++){
vis[i] = false;
}
return;
}
// function to get the transpose of the graph
void transposeGraph(vector<vector<int>>&adj, vector<vector<int>>&transpose){
for(int i=0;i<adj.size();i++){
for(auto it:adj[i]){
transpose[it].push_back(i);
}
}
return;
}
bool isMotherVertex(vector<vector<int>>&adj, int node){
int n = adj.size();
vector<bool>vis(n, false);
dfs(node, adj, vis);
for(int i=0;i<n;i++){
if(!vis[i]) return false;
}
return true;
}
// function to get the all mother vertices of the graph
vector<int> allMotherVertices(vector<vector<int>>&adj){
int n = adj.size();
vector<bool>vis(n);
// now we will try to find if there exist any mother vertex or not
// using the algorithm discussed above
int lastDfsCall = -1;
initializeVisited(vis);
for(int i=0;i<n;i++){
if(!vis[i]){
dfs(i, adj, vis);
lastDfsCall = i;
}
}
// now lastDfsCall may be the potential candidate for the
// mother vertex, so we will check whether this element is
// mother vertex or not, by running dfs on this, and check
// if all elements can be visited using this element
if(!isMotherVertex(adj, lastDfsCall)){
vector<int>v;
return v;
}
// now after checking the lastDfsCall is mother vertex, we
// will find all the SCC of this lastDfsCall
vector<vector<int>>transposeG(n);
// finding the transpose of the graph
transposeGraph(adj, transposeG);
// again making the vis vector
// false to keep the check on the visited array
initializeVisited(vis);
// dfs function
dfs(lastDfsCall, transposeG, vis);
// ans vector to store the final answer
vector<int>ans;
for(int i=0;i<n;i++){
if(vis[i]==true){
ans.push_back(i);
}
}
// return the ans vector
return ans;
}
int main(){
int v = 5;
vector<vector<int>>adj(v);
// graph given in sample case 2
adj[0].push_back(1);
adj[1].push_back(2);
adj[2].push_back(3);
adj[3].push_back(4);
adj[4].push_back(0);
// motherV to store the all mother vertices
vector<int>motherV = allMotherVertices(adj);
cout << "Total Number of mother vertices are : " << motherV.size() << endl;
// printing the mother vertices
for(auto it : motherV) cout << it << " ";
cout << endl;
}
You can also try this code with Online C++ Compiler
Output:
Total Number of mother vertices are: 5
0 1 2 3 4
Complexity Analysis
Time Complexity: O( |V| + |E |)
V is the number of vertices, and E is the number of edges since we are traversing only vertices and edges. Therefore the time complexity is O(|V| + |E|).
Space Complexity: O( |V| + |E |)
In the worst case, O(|V| + |E|) recursive stack space and O(V) space for the visited array.
Frequently Asked Questions
What is the difference between directed and undirected graph?
The directed graph contains ordered pairs of vertices while the undirected contains unordered pairs of vertices. In a directed graph, edges represent the direction of vertices, while edges do not represent the direction of vertices.
What is the maximum number of edges in the undirected graph of Nodes N?
Ans: Each node can have an edge over every other n-1 node in an undirected graph. Therefore the total number of edges possible is n*(n-1)/2.
Which data structure is used for iterative BFS and DFS of the graph?
Ans: In BFS, a queue data structure is used, while in DFS stack is used.
What is the difference between Breadth-first Search and Depth-first search?
The BFS uses queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.
Conclusion
In this article, we discussed the problem of finding all mothers of the graph, we have discussed the naive as well as an efficient approach for finding the mother vertices. We hope you understand the problem and solution properly. Now you can do more similar questions.
Check out this problem - Duplicate Subtree In Binary Tree
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.
Thank you for reading.
Until then, Keep Learning and Keep Coding.
85+ registered 