| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 162 |
| 3 | Um_nik | 161 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 148 |
I'm new to graphs. Currently I know how to use DSU on undirected graphs but I have a question whether DSU can be used for directed graphs or not? And of course, if possible, please share the solution, as well as some places to practice this DSU part.
P/s: I'm just a newbie so I hope everyone can help. Thank you very much.
Hello, it depends on your definition of connectivity. But generally, read about SCC (Strongly Connected Components); you might find the answer.
Thank you so much, I will try it
It's possible just depends upon what you mean by connected components like do you mean you can travel from one point to the ultimate parent or from ultimate parent to the node. And also a point can have multiple parents and as they may no necessarily merge into one. It will be difficult to implement and will also take away lots of advantages of DSU like been able to find no. of connected components, time complexity will be much higher is edge cases even O(n) making DSU pointless. There might be a different implementation which might allow for better working but as per my knowledge that's all. So in short it is possible but i wouldn't call it DSU any longer!
Yes, you're right. I tried it but the complexity is quite large, making it impossible for me to change the problem so I want to find a better solution.