EDGEDIR - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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.

RELATED PROBLEMS:

What will be it’s time complexity, Since it passed test cases, it shouldn’t be n^2 but can you explain where is my logic is going wrong…

suppose the odd indegree nodes are at the two ends of graph, you invert one, and let the inversion continue until it reaches its complement which is at the other end. This should take O(n) eg. case of graph as straight chain. Now if the number of odd indegree nodes is some n/k, then the time complexity should shoot upto n^2 ???

Expected time complexity is linear.
You logic is not wrong. But problem is you are directly implementing what was used to explain.

This is what you have ignored in editorial -
“You may process such queries in offline with simple dp counting number of vertices with odd indegree in each’s vertex subtree.”

1 Like

So In first dfs, you store number of subnodes with odd indegree, and in second one, you find the path which contains such nodes, and invert all nodes in these paths (while returning to root ) resulting linear time complexity ?? Did I understand correct now ??

1 Like