class Graph {
    public int vertexs; // 顶点个数
    public char[] data; // 顶点标识
    public int[][] weight; // 邻接矩阵（边的权值）
    public int edg_num; // 边的条数
    
    public Graph(int vertexs, char[] data, int[][] weight) {
        if (vertexs != data.length || weight.length != vertexs || weight[0].length != vertexs) {
            throw new RuntimeException("初始化异常！");
        }
        this.vertexs = vertexs;
        this.data = data;
        this.weight = weight;
    }
}

public class Prime {
    final static int MAX = Integer.MAX_VALUE;
    
    private static int[] prim(Graph graph, int start) {
        int[] visited = new int[graph.vertexs];
        int[] res = new int[graph.vertexs];

        for (int k = 1; k < graph.vertexs; k++) { // 循环n-1次
            int minWeight = MAX;
            int h1 = -1;
        	int h2 = -1;
            for (int i = 0; i < graph.vertexs; i++) {
                if (visited[i] != 1) continue;
                for (int j = 0; j < graph.vertexs; j++) {
              		if (visited[j] == 0 && graph.weigth[i][j] < minWeight) {
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            res[h1] = h2;
        }
        return res;
    }
}

// 需要实现lang包下的接口 这样可以直接进行排序
class Edg implements Comparable<Edg> {
    public int start;
    public int end;
    public int dis;
    // 方法省略
    ...
}

public class Kruskal {
    final static int MAX = Integer.MAX_VALUE;
    
    private static void kruskal(Graph graph) {
        Edg[] edges = new Edg[graph.edg_num];
        int index = 0;
        for (int i = 0; i < graph.vertexs; i++) {
            for (int j = i + 1; j < graph.vertexs; j++) {
                if (graph.weight[i][j] != Integer.MAX_VALUE) {
                    edges[index++] = new Edg(graph.data[i], graph.data[j], graph.weight[i][j]);
                }
            }
        }
        
        Arrays.sort(edges, (a, b) - > (a.dis-b.dis)); // 对边进行排序
        int[] res = new int[graph.vertexs];
        for (int i = 0; i < graph.vertexs; i++)
            	res[i] = i;
        int count = 0; // 需要找到节点数-1条边
        for (int i = 0; i < edges.length && count < graph.vertexs; i++) {
            Edg edg = edgs[i];
            int start_root = find(res, edg.start);
            int end_root = find(res, edg.end);
            if (start_root != end_root) {
            	count ++;
                res[end_root] = start_root;
            }
        }
        return res;
    }
    
    private static int find(int[] res, int i) {
        int i_root = i;
        while (res[i_root] != i_root)
            	i_root = res[i_root];
        return i_root;
    }
}