Although i understood the solution given in usaco guide but still i cannot convince myself why the following statement always produce correct result? Direct all edges that aren't part of this tree "upwards".
i’ve already read the cf blog given in guide but still cannot get intuition behind this.
Any help would be appreciated.
relevent code
void dfs(int u,int p){
vis[u] = timer++;
trav(v,adj[u]){
if(v==p) continue;
if(vis[v]!=-1){
if(vis[v] <= vis[u]){ // check if it is backedge that is going from child to its ancestor
odd[u] =odd[u]^1;
ans.push_back(mp(u,v)); // assign upward edge why?
}
}
else{
dfs(v,u);
if(odd[v]) {ans.push_back(mp(v,u)); odd[v]=0;}
else{ ans.push_back(mp(u,v)); odd[u] =odd[u]^1;}
}
}
}
Here’s a different (but ultimately similar) way to think about a solution to the problem.
Imagine you are solving a completely different problem, given a tree with vertices labeled either 0 or 1. You must decide the directions of each edge to make all vertices equal to 0. Like the original problem, setting an edge away from a vertex toggles its value.
In this simple problem, there is a very simple greedy solution. If a leaf has a value of 1, the edge adjacent to it must be an out edge to make it 0. Otherwise, it must be an inward facing edge because making it an out edge would make it 1 and there are no other edges incident to it to fix it. After you have resolved a leaf, remove it from the graph, and if the edge is an in edge change the value of the parent.
Eventually you will end up with a single node after applying the greedy algorithm for many steps. The value of the node is 0, then our algorithm found a correct configuration.
How do we know in the case that our algorithm fails to find a solution there are none? Denote the sum of the nodes initial states A and the number of edges M. All we care about is the parity of A. Note that every time we assign an edge we add 1 mod 2 to a node changing the parity of A. Hence the final parity of A is A + M mod 2. Obviously if this is odd then there are no solutions. Therefore the case where we end up with one odd node A was odd from the beginning, meaning there were no solutions for our greedy algorithm to find.
Now how does this simplified problem help us with the one at hand? Well, we have demonstrated that we can always solve it on any arbitrary tree with nodes preset to degrees of either even (0) or odd (1). Therefore it doesn’t matter which trees we choose as long as they cover as many nodes as possible. We can create an arbitrary set of spanning trees in our graph to make one to run our algorithm on by finding them and setting all edges not in the tree arbitrarily.
DFS in the model solution is simply an easy way of constructing these trees. A more traditional algorithm using DSU can alternatively be used to construct these if one prefers.
I was thinking about the same question, and I guess it doesn’t really matter which direction you are choosing for the back-edges, as long as you are directing them all in the same fashion (either all upwards or downwards), and a solution when all back-edges are directed downwards passes all tests as well.
Let me know if by now you have an explanation for this or some solid proof
I maybe thought about the problem in a more general way, which makes the proof verbose. But I think it’s somewhat intuitive.
First, I guessed that the following property holds: Property Suppose a connected component has n edges.
if n is even, you can orient the edges so that every node has an even outdegree
if n is odd, you can orient the edges so that exactly one node has an odd outdegree
You can prove this by induction. For example, consider case where n is even. Pick a random edge and remove it from the graph. There are two possibilities:
The graph remains one component, in which case we can orient the removed edge arbitrarily. By induction there exists a way to finish orienting the edges so that all outdegrees are even
The graph splits into 2 components (i.e. the edge removed was a bridge), one with an odd number of edges and one with an even number of edges. Then orient the removed edge towards the component with an odd number of edges and again by induction there exists a way to finish orienting the edges so all out degrees are even.
Then for the algorithm, it’s too complicated to implement the above, (although it’s doable with online bridge finding). But the characterization is very convenient–we can consider a leaf of the DFS tree and see that pointing all back edges out and deciding on the direction of the tree edge based on the parity of deg(leaf) will never make an orientable graph unorientable.
Edit: by the way, this characterization of when a graph is orientable answers @hocus_p0cus point about the direction of the backedges not mattering, since we can prove a related property: Property: In a connected graph with e edges, you can orient the edges so that vertices v_1, v_2, \dots v_k vertices have odd outdegree, as long as e and k have the same parity. Proof: We already know how to orient the edges so that either 0 or 1 vertex has an odd outdegree, depending on the parity of e. Orient the vertices accordingly.
Then there are an even number of vertices v_1, v_2, \dots, v_{2m} that need the parity changed.
Simply pair up the vertices and consider paths (on the undirected graph) v_1\rightarrow v_2, v_3\rightarrow v_4, \dots.
For every path, reverse the orientation of all edges on the path, which changes the parity of the outdegree only of the endpoints. Then the resulting orientation has exactly k vertices of odd outdegree.
