Friday, December 21, 2012

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!


3 comments:

  1. Thank you so much! I still don't quite understand it, but it works!

    ReplyDelete
    Replies
    1. The conditions for an Euler path to exist in a simple graph are: (a) All nodes must have even number of degrees. (b) If there are odd degree nodes, there will be even number of nodes with odd degrees. You just need to find a path given that there always one such path exists.

      Delete