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?

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 16:31:07 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

Then we can check whether the last finished vertex is mother or not by a single dfs or bfs. Is it correct now.

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.

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.

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.

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.

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.

MZuenni's approach seems a lot simpler, anyway thanks for your approach.

This is the most easier solution i have got but i do not know whether it will work for non-directed graph

codeWhat if the graph is disconnected ??? then mother vertex is -1 ... where this case is handeled by your code?

nopes, you need to run dfs again assuming top element is mother vertex ..