SPOJ PRIMIT

Problem link: SPOJ Problem Set (classical): 211. Primitivus recurencis

Given a list of directed edges or features, we have to find the smallest possible sequence of nodes where all the given edges are present without violating the direction.

Although at first this may seem to be a bipartite matching problem or problem related to strongly connected component. But I am not sure whether this particular problem can be solved using any of those techniques. Here we have two things to observe.

1 ⇒ Ordering for each weakly connected component is independent. So, we can add up the results for each weakly connected component as we can arrange them in any order, because they don't have any node in common.

2 ⇒ The minimum length will be the length of eulerian circuit for each component. We can break the circuit at suitable places to make it a chain. Considering [1], we can break the chain anywhere we want. Because other components have nothing to do with it.

So, for each weakly connected component, it boils down to finding minimum number of edges need to be added to make the component an euler circuit. For each component G_i, we can find the minimum number of additional edges by the following formula (Note, the formula will also handle the components which are already an euler circuit).

Number of additional edges = ∑max( cnt(Gi) / 2, 1 ) for all i

Note: if you already have an euler circuit, i.e. cnt(G_i) = 0, then you still need 1 additional term in the sequence. The simplest example is two edges, 1-2 and 2-1. You will need either 1-2-1, or 2-1-2 sequence.

And to find the value of cnt() for a component G_i, we just add the absolute difference of in and out degree count for each node in that component.

cnt(Gi) = ∑|d+(u) - d-(u)| for each u ∈ Gi
Here, d+(u) ⇒ indegree count for u, and d-(u) ⇒ outdegree count for u.

So, the overall solution outline is something like this, first use disjoint set data structure, or commonly known as union-find to mark the components. You can also use simple DFS / BFS as well. Ofcourse we are ignoring direction in this stage as we want to generate weakly connected components. Then for each node, calculate total indegree and outdegree counts. Now for each component, use the above formula to find additional edges x_add, thus the final answer is N + x_add, here x is the given number of edges.