[UOJ 168] Jungle

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 4/5
Implementation : 3/5
Just a friendly reminder that this problem is out of IOI syllabus, although it may not look like.

Problem link

Link in simplified chinese by shanquan2.

Simplified Statement

Given an undirected graph of $N \le 2000$ nodes, determine whether it is possible to color every edge into either pink or purple, such that edges of each color form a forest.

Full solution

So in these kind of problems, there are two directions. One is to think from construction, one is to think from impossible cases. The second direction works very good here. Usually, after you eliminate very obvious impossible cases, then all the remaining cases are possible. So in this problem, a very obvious observation is that the number of edges $M \le 2N-2$, otherwise it will be impossible. However, it is not strong enough. A generalization would be, for every non-empty subset of nodes $S$, the number of edges in the corresponding induced subgraph $S_M \le 2 \times |S| -2$. In easier words, it means that for every subgraph the number of edges must not be too many.

It turns out that this is sufficient!!! I'll try to demonstrate a construction, if for all subgraph $E \le 2 \times V -2 $ holds. I'll construct by induction.
When $n=1$ easy.
Assume $n>1$
Pick a node $u$ such that it has minimal degree.
By pigeon-hole principle its degree is $\le 3$.
Remove $u$ and construct solution.
If degree $\le 1$ trivial.
If degree $= 2$ then color one edge purple one edge pink.
So $u$ has a degree of $3$. Lets call its neighbours $a$, $b$ and $c$.
Define a full set to be a set that corresponding induced subgraph has $E=2 \times V-2$.
Claim 1: If $S$ and $T$ are full sets, then $S \cup T$ is also full.
Proof 1: If its not full, consider $S \cap T$, $E > 2 \times V -2$ so contradiction occurs. qed
Claim 2: There must exist a pair $(x,y)$ among $a$,$b$ and $c$, such that there is no set that includes both $x$ and $y$ and is full.
Proof 2: Assume otherwise, Let $P$,$Q$,$R$ be the three sets that include each pair. Then $P \cup Q \cup R \cup u$ would have $E = 2 \times V -1 $.qed
Now, take the current graph, remove $u$ and add edge $x - y$. It can be easily seen that this graph also have "for all subgraph $E \le 2 \times V -2 $ " held. Construct solution for this graph. Remove $x-y$ and add $x-u$ and $y-u$ using the color of $x-y$. Then color the last edge incident to $u$ with the opposite color. Then this coloring is also valid.qed.

So now, we have to find out how to check if for all subgraph $E \le 2 \times V -2 $ holds, which is some flow that i dont want to describe too much detail because it is very technical. Basically you have to know how to do "largest weight closed subgraph" using flow, then you realise that you have to repeat $V$ times, fix a vertex to exist in the set and run this thing to find the subgraph with largest $E-2 \times V$. This would give $N^3$ and 80% of the points. To get $N^2$, you just have to realise that each time you run the flow the graph changes only a little bit, and you can improve with retracting flows.

Geniosity's comments

3 seconds after reading problem: This is just matroid intersection!!! Matroid 1 = pick two sets of edges such that no edge is repeated. Matroid 2 = pick two sets of edges such that set is acyclic.
Few more seconds later: I see this problem in ROM before. Its just check whether there is subgraph that has $E \gt 2 \times V -2$. Then can flow...