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?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 18:05:50 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
Just to dfs and store the mother vertex in a variable, the last stored vertex in the variable might be a mother vertex, at the end you have to check if this vertex can access all the vertex, if it can then it is a mother vertex else no.
In other words:
Lemma: If a mother vertex exists, it will be the last value entered in the Mother variable.