Kruscal - nise-nabe/topcoder GitHub Wiki

    static class Kruskal {
        int n;
        List<int[]> edges;
        int unusedMax;

        Kruskal(int n) {
            this.n = n;
            edges = new ArrayList<>();
        }

        void addEdge(int u, int v, int cost) {
            edges.add(new int[] { u, v, cost });
        }

        void init(int unusedMax) {
            this.unusedMax = unusedMax;
            edges.sort(Comparator.comparingInt(o -> o[2]));
        }

        List<int[]> getEdges(int b) {
            UnionFind uf = new UnionFind(n);
            List<int[]> result = new ArrayList<>();
            for (int[] edge : edges) {
                if (!(edge[0] < unusedMax && !((b & 1 << edge[0]) < 1))
                    && !(edge[1] < unusedMax && !((b & 1 << edge[1]) < 1))
                    && !uf.isSame(edge[0], edge[1])) {
                    uf.unite(edge[0], edge[1]);
                    result.add(edge);
                }
            }
            return result;
        }
    }


    static class UnionFind {
        int[] par;
        int[] rank;

        UnionFind(int n) {
            par = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; ++i) {
                par[i] = i;
                rank[i] = 0;
            }
        }

        int find(int x) {
            return par[x] == x ? x : (par[x] = find(par[x]));
        }

        void unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y)
                return;
            if (rank[x] < rank[y]) {
                par[x] = y;
            } else {
                par[y] = x;
                if (rank[x] == rank[y])
                    ++rank[x];
            }
        }

        boolean isSame(int x, int y) {
            return find(x) == find(y);
        }

        int size() {
            java.util.Set<Integer> set = new java.util.HashSet<>();
            for(int p : par) {
                set.add(find(p));
            }
            return set.size();
        }
    }