Contest Duration: - (local time) (100 minutes) Back to Home

## C - Keep Graph Connected Editorial by evima

It turns out there is always a solution for a tree. Thus, we just need to randomly choose some spanning tree of the graph and consider only that tree. Below is one possible algorithm to find a good way of writing integers on a tree.

Let us make the tree rooted and write integers from the root to the bottom. We first write $$1$$ on the root, then write numbers on the vertices just beneath the root, and so on. When we write a number on some vertex $$u$$, the parent $$p$$ of $$u$$ already has a number written. If the number on $$p$$ equals the label of the edge, we write some other number; otherwise, we write the number that is the label of the edge.

It can work in $$O(N+M)$$ time, and it is fast enough.

posted:
last update: