| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 4039 |
| 2 | tourist | 3841 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3590 |
| 5 | ecnerwala | 3542 |
| 6 | Benq | 3535 |
| 7 | orzdevinwang | 3526 |
| 8 | gamegame | 3477 |
| 9 | heuristica | 3357 |
| 10 | Radewoosh | 3355 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | -is-this-fft- | 165 |
| 3 | atcoder_official | 160 |
| 3 | Um_nik | 160 |
| 5 | djm03178 | 158 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 153 |
| 8 | luogu_official | 151 |
| 8 | awoo | 151 |
| 10 | TheScrasse | 147 |
There is a graph (might have cycles) in the form of an adjacency list. How can we find the 'size' of the largest connected component?
Example: 0: 1 2 1: 2: 1 3 3: 1 2 4 4: 2 3
Answer: 5 Reason: We start from 0 and go to 1 and 2, from 2 we can reach 3, from 3 we can reach 4.
What can be the most efficient way to calculate this?
You can traverse the graph with DFS, and keep track of the visited nodes. For each node, you start DFS if it's not visited. Then you increment your size counter each time you discover a new neighbor and set it to visited, and you take the max size. It's
O(n)I believeyou can do DSU that stores the lengths of each component
This is a standard problem. What you are referring to is, in the case of a directed graph, the notion of a "strongly connected component". There are a bunch of algorithms that do this such as Trajan's algo. You can find blogs discussing it on cp-algorithms and usaco.guide