http://codeforces.net/problemset/problem/28/B
The writer provides a simple solution,but I don't know how to prove the solution is correct. Who can explain it?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 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 | 151 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/23/2024 08:26:53 (l3).
Desktop version, switch to mobile version.
Supported by
You are given a graph. Each vertex is assigned some unique value. Then you are allowed to exchange assigned values for any two vertices connected with an edge. The question is what assignments you can derive using the above operation any number of times.
Apparently, you can't move a value into other connected component than it has been assigned to before any exchanges. Also it's rather easy to prove that within one connected component you can get any assignment (of course, providing it uses the same set of values as the original one). The idea for the proof is that in a connected graph you may find a vertex that is not an articulation point (i.e. it keeps graph connected when removed), so you may safely put correct value into it and then remove it.
So the solution for original problem would be: for each vertex i check that it is in the same connected component of "allowed swaps graph" as vertex with index value(i).