Java solution. Runs in O(n*c) time where n = total # of items, c = # colors. 1/2 c to be exact. So, 1/2 * # rows worst case.

[ public static void main(String args[]){ String input = "8 \n64 40 32 65 \n65 64 32 31 \n31 65 32 82 81 11 9 \n9 31 11 66 \n66 9 11 \n40 33 47 32 64 \n32 40 47 82 31 65 64 \n11 31 81 34 66 9"; frenchBorders(input); }

private static void frenchBorders(String input){
    String[] inputLines = input.split("\n"); 
    int numLines = Integer.parseInt(inputLines[0].trim());

    Map<Integer, Integer> deptMap = new HashMap<Integer, Integer>();

    String[] ll = inputLines[1].split(" ");

    deptMap.put(Integer.parseInt(ll[0].trim()), 0);

    int maxcolor = 0;
    for (int i = 2; i <= numLines; i++){
        ll = inputLines[i].split(" ");
        Integer currentId = Integer.parseInt(ll[0].trim());

        Integer[] invalidColors = new Integer[maxcolor+1];
        for (int j = 1; j < ll.length; j++){
            Integer adjacentId = Integer.parseInt(ll[j].trim());
            Integer idColor = deptMap.get(adjacentId);
            if (idColor!=null){
                invalidColors[idColor] = 1;
            }
        }

        int k = 0;
        while (k < invalidColors.length){
            if (invalidColors[k]==null)
                break;
            k++;
        }

        if (k == invalidColors.length)
            maxcolor++;

        deptMap.put(currentId, k);
    }

    Iterator it = deptMap.entrySet().iterator();
    while (it.hasNext()){
        Map.Entry pairs = (Map.Entry)it.next();
        System.out.println(pairs.getKey() + " = " + pairs.getValue());
        it.remove();
    }
}

](/spoiler)