As I said before I think java programs should get higher time limit. My java program gets TLE on test #4 or #5 285ms.
In my opinion my program runs in O(nlogn). Below I gave the code that gets TLE:



import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> lst = new ArrayList<>();
        int[] sorted;
        PriorityQueue<Integer>[] g;

        int[] degree = new int[8000];
        Arrays.fill(degree, 0);

        // O(n)
        while (sc.hasNextInt()) {
            int tt = sc.nextInt() - 1;
            lst.add(tt);
            degree[tt]++;
        }

        g = new PriorityQueue[lst.size() + 1];
        sorted = new int[lst.size() + 1];
        // O(n)
        for (int i = 0; i < lst.size() + 1; i++) {
            sorted[i] = i;
            g[i] = new PriorityQueue<>();
        }

        // find initial leaves O(nlogn)
        PriorityQueue<Integer> leaves = new PriorityQueue<>();
        for (Integer y : sorted) {
            if (degree[y] == 0) {
                leaves.add(y);
            }
        }

        // O(nlogn)
        for (int x : lst) {
            degree[x]--;

            int y = leaves.poll();

            g[x].add(y);
            g[y].add(x);

            if(degree[x] == 0){
                leaves.add(x);
            }

        }

        // O(nlogn)
        for (int i = 0; i < g.length; i++) {
            System.out.print((i + 1) + ":");
            while (!g[i].isEmpty()) {
                System.out.print(" " + (g[i].poll() + 1));
            }
            System.out.println("");
        }

    }
}





Edited by author 12.12.2014 23:17

Oh gosh, I used buffered reader instead of Scanner.nextInt() and got AC, micro-optimizing your code for I/O is not the right thing for this problem IMO:
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");