aman_naughty's blog

By aman_naughty, history, 23 months ago,

I was wondering if we can find the mother vertex in a directed connected graph by topological sorting. The last finished vertex will be the mother vertex.

Is this approach correct or am I thinking wrong?

• +3

 » 23 months ago, # |   +6 I had to google what the hell a "mother vertex" was. Apparently it's a vertex $v$ such that any other vertex can be reached from $v$.And no, it's not correct. What if the graph has no mother vertices? Your algorithm will still try to say something is the mother vertex.
•  » » 23 months ago, # ^ |   0 Then we can check whether the last finished vertex is mother or not by a single dfs or bfs. Is it correct now.
•  » » » 23 months ago, # ^ |   0 Yes, but only in a DAG. (At least I think so, but from your blog the "last finished vertex" is a bit unclear.)If your however graph isn't acyclic, then the concept of topological sorting is meaningless.
 » 23 months ago, # | ← Rev. 3 →   +8 This vertex can be easily found with n times a dfs. Start a dfs from each unvisited vertex and only visit unvisited vertices. The last vertex where we started a dfs is the vertex we search(if any such vertex exists). However, a topological sorting may not work.
•  » » 23 months ago, # ^ |   0 Isn't topological sort doing the same thing as you mentioned? At the end of the topological sort, the last vertex in the stack will be a candidate for mother vertex.
•  » » » 23 months ago, # ^ |   0 its more or less the same as toposort with dfs. However there are other ways to get topological sortings kahns algorithm. This may fail. For example on a non DAG graph kahns algorithm will definitely fail.
 » 23 months ago, # |   +19 Find strongly connected components and build the DAG of SCCs , consider the first component in topological sort if that can visit all other components then all nodes in that Strongly connected component are "mother" vertices.
•  » » 23 months ago, # ^ |   0 MZuenni's approach seems a lot simpler, anyway thanks for your approach.
•  » » » 8 months ago, # ^ |   0 This is the most easier solution i have got but i do not know whether it will work for non-directed graph code#include using namespace std; vectoradj[100]; bool vis[100]; stacks; void dfs(int x) { vis[x]=1; for(int i=0;i>n>>m; for(i=1;i<=m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); } for(i=0;i
•  » » » » 7 weeks ago, # ^ |   0 What if the graph is disconnected ??? then mother vertex is -1 ... where this case is handeled by your code?
•  » » » » » 7 weeks ago, # ^ |   0 nopes, you need to run dfs again assuming top element is mother vertex ..