rminuv372's blog

round 28B
By rminuv372, 13 years ago, In English
http://codeforces.com/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?
  • Vote: I like it
  • -4
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
This problem is a particular case of the following one.

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).
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ym ... .
→ Reply