import java.util.*;

public class KruskalAlgorithm {
    
    // 定義邊的數(shù)據(jù)結(jié)構(gòu)
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
 
        public int compareTo(Edge edge) {
            return this.weight - edge.weight;
        }
    }
    
    // 并查集數(shù)據(jù)結(jié)構(gòu)
    class Subset {
        int parent, rank;
    }
 
    int V, E; // V是頂點(diǎn)數(shù)，E是邊數(shù)
    Edge edge[]; // 存儲邊的數(shù)組
 
    // 構(gòu)造函數(shù)，初始化邊和頂點(diǎn)數(shù)
    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }
 
    // 查找父節(jié)點(diǎn)
    int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }
 
    // 合并兩個子集
    void union(Subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
 
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
 
    // 執(zhí)行克魯斯卡爾算法
    void kruskal() {
        Edge result[] = new Edge[V]; // 存儲結(jié)果的數(shù)組
        int e = 0; // 表示result數(shù)組中的下標(biāo)
 
        // 將邊按照權(quán)重從小到大排序
        Arrays.sort(edge);
 
        // 創(chuàng)建V個子集
        Subset subsets[] = new Subset[V];
        for (int i = 0; i < V; ++i)
            subsets[i] = new Subset();
 
        // 初始化每個子集的父節(jié)點(diǎn)和秩
        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
 
        // 取E-1條邊
        int i = 0;
        while (e < V - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
 
            // 如果兩個節(jié)點(diǎn)不在同一個集合中，合并它們
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }
 
        // 打印結(jié)果
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i){
            System.out.println(result[i].src + " - " + result[i" - " + result[i].weight);
            return;
        }
        
        // 定義一個輔助函數(shù)，用于查找結(jié)點(diǎn)所在的集合 
        private int find(int parent[], int i) { 
            if (parent[i] == -1) 
                return i; 
            return find(parent, parent[i]); 
        }

        // 定義一個輔助函數(shù)，用于合并兩個集合 
        private void union(int parent[], int x, int y) { 
            int xset = find(parent, x); 
            int yset = find(parent, y); 
            parent[xset] = yset; 
        } 
    }
}