PROBLEM LINK:
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Spanning trees, dp on trees
PROBLEM:
You have undirected connected graph with N vertices and M edges. You have to direct edges of the graph in such a way that indegree of each vertex is even. (1 \leq N, M \leq 10^5)
QUICK EXPLANATION:
Direct edges in arbitrary way. Now you may choose any path in initial graph and inverse all edges on this path. In such way you will change indegrees only of first and last vertices on the path, thus you may group vertices of odd indegrees in pairs and get rid of them.
EXPLANATION:
Assume that edges of the graph are already directed in some way. What will happen if we inverse edge u \to v? Parities of indegrees of both u and v will inverse as well, because u will have one more edge among edges directed to it and v will lose one such edge. This is the simplest case of edge inversion and any other one may be simply reduced to it. Note that parity of vertices having odd indegree will never change when inverting one edge, this gives us simple criteria of when solution exists: Solution exists \iff amount of vertices having odd indegree is even.
Now what to do if solution exists? Consider path v_1 \to v_2 \to \dots \to v_{k-1} \to v_k. What will happen if we invert all edges in such path? Answer is that parity of indegrees of v_1 and v_k will be inversed and parity of v_2, \dots, v_{k-1} won’t change. Thus if amount of vertices having odd indegrees is even, you may make them in pairs in arbitrary way and one by one inverse all edges in pathes between vertices in each pair. And now you have pretty vast space on implementation of this.
First of all you should note that you may always choose path from some spanning tree (e.g. dfs tree). This would reduce problem to “invert edges on the path in tree several times, output final state of each edge”. And now you may either honestly group vertices in pairs and do such queries with some data structure or you may see that inverting path between u and v is the same as firstly inverting path from u to w and then from v to w where w is arbitrary vertex in the tree. This provides you with easiest solution if you simply choose w to be the root of the tree. Then no matter how you split vertices in pairs, you will simply need to invert all edges in set of pathes w \to v_1, w \to v_2, \dots, w \to v_k where v_1, \dots, v_k is the set of vertices having odd indegree and w is the root of the tree. You may process such queries in offline with simple dp counting number of vertices with odd indegree in each’s vertex subtree.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.