I am solving this DIV 2C. This is my submission which got accepted.
My question is this:
Why isn't updating the parent of a node, an O(n) operation ?
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 08:50:13 (k3).
Desktop version, switch to mobile version.
Supported by
You are constructing the disjoint set using path compression. i.e. When you look for the father of a node, each node on the path to the root remember the father, so the complexity is not linear per query. If you want to be even more sure about the complexity you should do rank compression, i.e. remember for each tree their height, and make the shorter tree child of the taller tree (the one with highest height). The overall complexity per query is ackerman inverse per query (amortized).
More info about Disjoint Set.