Euler Tour

SRM 185 EulerianRace, given a graph where node degree's are even, construct euler tour, according to some rule. Start from 0, build a cycle, if every edge is visited we're done. Other wise check from start of current cycle, which node has unvisited edge, find again cycle from that node. Insert the new cycle in between.

What to do in this problem is clear, how to do it ? also somewhat clear. I had planned this implementation, but as always, the devil is in the details. The most time I spent when practicing this problem is to realize the mistakes in inserting cycles to existing cycle using list.add(index,element).

I have list 0,4 and I wanted to insert 1,2,3, inserting one by one this 1,2,3 always at the position after element 0, seems like something logical. But it turns out it produces 0,3,2,1,4 instead of 0,1,2,3,4. So next time I wanted to insert a list into a list with this, I should remember to increase the index.

import java.util.*;
public class EulerianRace {
    int n, start, split;
    int[] d;
    boolean[][] b, u;
    LinkedList < Integer > res = new LinkedList < Integer > ();

    public int[] planRoute(String[]bridges) {
        n = bridges.length;
        u = new boolean[n][n];
        b = new boolean[n][n];
        d = new int[n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                b[i][j] = bridges[i].charAt(j) == '1';
                if (b[i][j]) d[i]++;
            }

        res.add(0);
        split = 0;
        while (split != -1) {
            split = -1;
            for (int i = 0; i < res.size(); i++)
                if (d[res.get(i)] > 0) {
                    split = i;
                    start = res.get(i);
                    go(start); break;
                }
        }

        int[] ret = new int[res.size()];
        for (int i = 0; i < res.size(); i++)
            ret[i] = res.get(i);
        return ret;
    }
    void go(int cur) {
        res.add(split++, cur);
        for (int i = 0; i < n; i++)
            if (b[cur][i] && !u[cur][i]) {
                u[i][cur] = u[cur][i] = true;
                d[cur]--; d[i]--;
                if (i != start) go(i);
                break;
            }
    }
}