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.

USACO 3.3 fence

Section 3.3: Riding the Fences

This is just another simple Euler path problem. Given a undirected unweighted graph, which contains multiple edges, you have to find the lexicographically smallest Euler path.

I don't know what the problem setter was thinking, but he made a big mistake. Problem statement says "Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude." where nodes are numbered from 1 to 500. Clearly, 500 is not a base 500 digit. I made several wrong submissions for trying to do some foolish tricks to get this done, then I just did a lexicographic ordering, and it passed. Pretty funny!

Problem statement ensures that there is no input for which Euler path does not exist. This makes the solution easier, just check if all the degrees are even, if so, start from the smallest numbered node, otherwise start from smaller numbered odd degree node.

algorithm for finding euler path:
graph[u][v] contains number of edges between u and v

find( node u ):
    for each adjacent v of u in lexicographical order:
        while( graph[u][v] > 0 ):
            graph[u][v]--;
            graph[v][u]--;
            find(v);
    stack.push(u);

Now the stack contains the euler path in reverse order, so just keep popping!

Euler Tour

A famous drawing problem for kids, "You are given a picture, can you draw it without lifting up your pen?"... Well, in graph theory, we can determine this by checking the Euler Tour in the graph.


Actually this is about Euler Circuits and Eluer Paths. We know the conditions for an undirected graph, and we can extend it for directed graphs as well.

Undirected Graph

An undirected graph will have Eulerian tour ( either path or circuit ) if the following conditions hold:

• The graph is connected.
• Each node has even degree, or exactly two nodes have an odd degree.

Directed Graph

A directed graph will have Eulerian tour ( either path or circuit ) if the following conditions hold:

• The undirected representation of the graph is connected.
• The difference between indegree and outdegree of each node is at most 1.
• Each node has equal indegree and outdegree, or, there is exactly two nodes which has different indegree and outdegree, and exactly one of them has indegree - outdegree = 1 and the other has outdegree - indegree = 1.

So, we can do this easily with the help of a bfs subroutine.
You might also like to read this and this.