PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The problem is asking you to orient a subset of the edges in an undirected graph so each node has out-degree exactly 1. This should be done while maximizing the total value of the edges that were oriented. Now, a set of edges F can be oriented so each node has out-degree exactly 1 if and only if every connected component in the graph using only edges in F has exactly one cycle. Necessity is easy to see (consider the set of edges that were oriented and “undirect” them to see this) and sufficiency follows by orienting the edges on the cycle to create a directed cycle and orienting all other edges toward this cycle (it’s like a tree with a cycle for the root instead of a single node). So, the problem really boils down to finding the highest total value subset of edges such that each connected component using these edges has a unique cycle.
This can be solved with a greedy algorithm that is similar to Kruskal’s maximum spanning tree algorithm. Initialize a set of edges F to empty and consider the edges in decreasing order of value. When considering an edge e, add e to F if and only if it does not create a connected component in F having more than one cycle. Sorting takes O(M log M) time and the remaining part of the algorithm can be done using the union find data structure while keeping track of one additional bit of information at each component that indicates if the component already has a cycle or not. Thus, the entire algorithm takes O(M log M) time (assuming, of course M >= N, but there cannot be a solution otherwise).
Now, one can prove that the collection of subsets of edges where each subset has at most one cycle per connected component forms a matroid commonly called the “bicircular matroid”. This immediately implies correctness of the above algorithm if you are familiar with such concepts. However, I’ll argue correctness in a more down-to-earth fashion (which is similar to proving it is a matroid). Sort the edges e _ 1, …, e _ M in non-increasing order of value. If there is no solution then the greedy algorithm clearly can’t find one. Now, assume there is a solution and let K be an optimum solution. Let F be the collection of edges used in our greedy algorithm (which we still haven’t even proven form a valid solution). Consider the least index i such that e _ i is in exactly one of K or F (i.e. the least index the greedy solution F disagrees with the optimum solution K). It must be that e _ i is in F but not K since we greedily take any edge we see (if possible).
Now, adding e _ i to K does one of two things. It either increases the number of cycles in a connected component in K or it bridges two connected components in K, each of which already has one cycle. Consider the latter case (the arguments for the former case are analagous). Let A and B denote these cycles and let C denote the path (including e _ i) connecting these cycles. Now, there is some edge in A,B, or C that is not in F since F does not have any component with two cycles (by construction). Say this edge is e _ j. Notice that j > i since i is the least index where F and K disagree on e _ i. Consider the set of edges K + {e _ i} - {e _ j}. Regardless of whether e _ j is in A,B or C, this new set is a feasible solution (it either destroys one of the cycles A or B or it separates them again). It’s cost hasn’t increased since j > i. Therefore, we arrive at a new optimum solution that agrees with our greedy solution F on the first >=i edges. Continue this process to see that there is an optimum solution that agrees with our greedy solution so F must be a) feasible and b) optimum.