Swapping some operations to

Question

Assume we have got an array arr with all initial values 0. Now we are given n operations - an operation consists of two numbers a b. It means that we are adding +1 to the value of arr[a] and adding -1 to the value of arr[b].

Moreover, we can swap numbers in some operations, what means that we will add -1 to arr[a] and +1 to arr[b].

We want to achieve a situation, in which all values of arr are equal to 0 even after all these operations. We are wondering if that is possible, and, if yes, what operations should we swap to achieve that.

Any thoughts on that? Some example input:

3
1 2
3 2
3 1

should result in YES R N R where R means to reverse that operation, and N not to do it.

input:

3
1 2
2 3
3 2

results in answer NO.

Answer 1

Let each of the array element be a vertex in a graph and the operation (a,b) be a edge from vertex a to b (there might be multiple edges between same vertices). Now traveling from the vertex a means decrease array element a and traveling to the vertex a means increase array element a. Now if each vertex has an even number of edges and you find a cyclic path that visits each edge exactly once you will have a zero total sum in the array.

Such a path is called Eulerian cycle (Wikipedia). From the Wikipedia: An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. As in your case only all the disconnected sub graphs need to have an Eulerian cycle it is enough to count how many times each array index appears and if the count is even for each one of them there is always way to obtain zero total in the array.

If you want to find out which operations to reverse, you need to find one of such paths and check which directions you travel the edges.