What algorithm should I use to find the number of rooted trees in an undirected graph? This problem requires it
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.12.2024 03:07:13 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
No, it doesn't. You just need to check if the graph has only one cycle and is connected. It can be done with a simple DFS or with DSU. See here -> 22406598
Can you please prove how you deduced it to the above properties?
Suppose we have a tree with n nodes. Thus, it has n — 1 edges. Now whenever i join an edge between any two nodes in the tree(connect two existing nodes, non adjacent), a cycle of at least 3 nodes will be formed. Thus the new graph should have n edges and has only one component.
Well, there's another kind of a time consuming way to solve it. First find if a cycle in the graph. Then check if there are no other cycles except the previously found one(run dfs rooted from the nodes from the previously found cycle and test for cycles while not visiting nodes of the previously found cycle) . Finally check if all nodes are in the same component.
I am sorry but while checking my code again I found a bug(fails on some case). The solution is wrong.