Kruskal can break early once the graph is connected in which case it doesn't have to process all edges. Thus, in cases like here, where the edges are dynamically ordered, not all edges may need to be prepared. I tested this idea below. It cuts the runtime drastically for many of the test cases (and I verified that, many break after only a few pe…

mstwithiterator.java

/*
Kruskal can break early once the graph is connected in which case it doesn't have to process 
all edges. Thus, in cases like here, where the edges are dynamically ordered, not all edges
may need to be prepared. I tested this idea below. It cuts the runtime drastically for many 
of the test cases (and I verified that, many break after only a few percent of the edges). 
It doesn't cut worst case time because for some of the larger tests, the graph isn't 
connected until over 99% of the edges are considered. But, it also doesn't hurt. 
In fact, Kattis runtime was .1s faster than the eager, array-based version, so 
the use of the Iterator doesn't hurt.  Note that the solve() method could also be 
written to take an Iterator, which would avoid the somewhat random construction 
of an Iterable. On the other hand, the Iterator for loop could be used if edges is an actual array.
*/
    
    // adjust weight of e2's by 'time', and sort up to ties2Before e3's before e2 where tied.
    private static int f(long time, int tiesBefore) {
        final Iterator<Edge> e = new Iterator<Edge>() {
            int idx2 = 0;
            int idx3 = 0;
            int ties = 0;

            @Override
            public boolean hasNext() {
                return idx2 < e2.size() || idx3 < e3.size();
            }

            @Override
            public Edge next() {
                long length2 = idx2 == e2.size() ? Long.MAX_VALUE : e2.get(idx2).l + time;
                long length3 = idx3 == e3.size() ? Long.MAX_VALUE : e3.get(idx3).l;
            
                if (length2 < length3) {
                    return e2.get(idx2++);
                } else
                if (length2 > length3) {
                    return e3.get(idx3++);
                } else {
                    // tie. Some e2's go before, some go after.
                    if (ties++ <= tiesBefore)
                        return e3.get(idx3++);
                    else
                        return e2.get(idx2++);
                }
            }
        };

        return solve(n, new Iterable<Edge>() {
            public Iterator<Edge> iterator() {
                return e;
            }
        });
    }
    /*
     * Minimum Spanning Tree with Kruskal.
     * 
     * Uses eager union.
     */
    static class Edge {
        int p1, p2;
        long l;
        Edge(int p1, int p2, long l) {
            this.p1 = p1;
            this.p2 = p2;
            this.l = l;
        }

        public String toString() {
            return p1 + " " + p2 + " " + l;
        }
    }

    static long COST_RETURN = -1;
    // Kruskal's MSP algorithm
    static int solve(int V, Iterable<Edge> edges) {
        int count = 0;
        UnionFind union = new UnionFind(V);

        long len = 0;
        for (Edge e : edges) {
            if (union.find(e.p1) != union.find(e.p2)) { // find(p1) != find(p2)

                if (special[e.p1] != special[e.p2]) {
                    count++;
                }

                len += e.l; // add edge 'e' to MSP
                // merge cluster p2 into p1: union(p1, p2)
                union.union(e.p1, e.p2);
            }

            if (union.count == 1)
                break;
        }
        if (union.count != 1) {
            System.out.println(-1);
            System.exit(0);
        }
        // System.err.println(len + " " + count);
        COST_RETURN = len;
        return count;
    }