/**
 * 测试用例：
 * 请输入图的顶点和边的个数(格式：顶点个数 边个数)：7 11
 *
 * 请输入图的路径长度(格式：起点 终点 长度)：
 * 1 2 7
 * 1 4 5
 * 2 3 8
 * 2 4 9
 * 2 5 7
 * 3 5 5
 * 4 5 15
 * 4 6 6
 * 5 6 8
 * 5 7 9
 * 6 7 11
 *
 * 结果：
 * 第 1 步: 加入边 (1, 4) 权重为 5
 * 第 2 步: 加入边 (4, 6) 权重为 6
 * 第 3 步: 加入边 (1, 2) 权重为 7
 * 第 4 步: 加入边 (2, 5) 权重为 7
 * 第 5 步: 加入边 (5, 3) 权重为 5
 * 第 6 步: 加入边 (5, 7) 权重为 9

 * 总权值为：39
 */
 
import java.util.Scanner;
 
public class PrimMST {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		System.out.print("请输入图的顶点和边的个数(格式：顶点个数 边个数)：");
		int n = input.nextInt(); //顶点的个数
		int m = input.nextInt(); //边的个数

		System.out.println();

		int[][] a = new int[n + 1][n + 1];
		//初始化邻接矩阵
		for(int i = 0; i < a.length; i++) {
			for(int j = 0; j < a.length; j++) {
				a[i][j] = -1; //初始化没有边
			}
		}

		System.out.println("请输入图的路径长度(格式：起点 终点 长度)：");
		//总共m条边
		for(int i = 0; i < m; i++) {
			//起点，范围1到n
			int s = input.nextInt();
			//终点，范围1到n
			int e = input.nextInt();
			//长度
			int l = input.nextInt();
			
			if(s >= 1 && s <= n && e >= 1 && e <= n) {
				//无向有权图
				a[s][e] = l;
				a[e][s] = l;
			}
		}

		System.out.println();

		prim(a);
	}

	/**
	 * prim算法求解最小生成树
	 *
	 * @param c 图的邻接矩阵
	 */
	public static void prim(int[][] c) {
		int n = c.length;
		//判断节点是否放入的矩阵
		boolean[] s = new boolean[n];
		int[] lowcost = new int[n];
		int[] closest = new int[n+1];
		
		int totalWeight = 0;
		
		//放入顶点1
		s[1] = true;
		// 初始化
		for(int j = 2; j < n; j++) {
			lowcost[j] = c[1][j];
			closest[j] = 1;
			s[j] = false;
		}
		
		//共扫描n-2次，v到v自己不用扫
		for(int i = 1; i < n - 1; i++) {
			int min = Integer.MAX_VALUE;
			int j = 1;
			//找寻最短路径，记录点j和距离lowcost[j]
			for(int k = 2; k < n; k++) {
				if(lowcost[k] != -1 && lowcost[k] < min && !s[k]) {
					min = lowcost[k];
					j = k;
				}
			}
			System.out.println("第 " + i + " 步: 加入边 (" + closest[j] + 
				", " + j + ") 权重为 " + min);
			totalWeight += min;
			//将j添加到S中
			s[j] = true;
			
			//遍历整个图，用j更新lowcost数组
			//判断在新的点加入的情况下，是否有更短的路径
			for(int k = 1; k < n; k++) {
				if(!s[k] && c[j][k] != -1) {
					if(c[j][k] < lowcost[k] || lowcost[k] == -1) {
						lowcost[k] = c[j][k];
						closest[k] = j;
					}
				}
			}
		}
		
		System.out.println("\n总权值为：" + totalWeight);
	}
}

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

public class KruskalMST {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("请输入图的顶点和边的个数(格式：顶点个数 边个数)：");
        int n = input.nextInt(); // 顶点的个数
        int m = input.nextInt(); // 边的个数

        Edge[] edges = new Edge[m];

        System.out.println("请输入图的路径长度(格式：起点 终点 长度)：");
        // 总共m条边
        for(int i = 0; i < m; i++) {
            Edge edge = new Edge();
            //起点，范围1到n
            edge.u = input.nextInt();
            //终点，范围1到n
            edge.v = input.nextInt();
            //权重
            edge.weight = input.nextInt();

            edges[i] = edge;
        }

        System.out.println();

        // 对数组进行排序
        Arrays.sort(edges, new Comparator<Edge>() {

            @Override
            public int compare(Edge e1, Edge e2) {
                // 返回值为int类型，大于0表示正序，小于0表示逆序
                return e1.weight - e2.weight;
            }
        });
        
        kruskal(n, edges);
    }
	
    /**
     * kruskal算法求解最小生成树
     *
     * @param n 顶点的个数
     * @param edges 存储边信息的集合
     */
    public static void kruskal(int n, Edge[] edges) {
        DSU dsu = new DSU(n);
        
        // 最小生成树的总权值
        int totalWeight = 0;
        // 已加入边的数量，比顶点的数量小1.
        int m = 0;
        
        for(Edge e : edges) {
            if(m == (n - 1)) {
                break;
            }
            int u = e.u;
            int v = e.v;
            int w = e.weight;
            
            // 两个节点不属于一个连通分量
            if(dsu.findRoot(u) != dsu.findRoot(v)) {
                totalWeight += e.weight;
                dsu.union(u, v, w);
                m++;
            }
        }
        
        System.out.println("总权值为：" + totalWeight);
    }
}

/**
 * 存储边信息的类
 */
class Edge {
    public int u, v;
    public int weight;
}

/**
 * 并查集(Disjoint Set Union)类
 */
class DSU {
    /**
     * 记录每个节点根节点的数组
     */
    int[] root;
    /**
     * 记录图的连通分量
     */
    int[] size;
    
    /**
     * 构造函数
     * 
     * @param n 图的顶点的数量
     */
    public DSU(int n) {
        /**
         * 存储每个节点的根节点
         */
        root = new int[n + 1];
        /**
         * 存储图的每个连通分量的尺寸
         */
        size = new int[n + 1];
        
        // 将图当作森林，每个节点一开始都是一棵树。根节点是其自身
        for(int i = 0; i < root.length; i++) {
            root[i] = i;
        }
        
        // 将图当作森林，每个节点一开始都是一棵树，尺寸为 1
        Arrays.fill(size, 1);
    }
    
    /**
     * 寻找目标节点的根节点
     *
     * @param x 目标节点
     */
    public int findRoot(int x) {
        // 如果节点有根节点，即该节点已经加入了其它树中
        if(root[x] != x) {
            // 路径压缩，即只存储了根节点的信息，并未存储父节点的信息
            root[x] = findRoot(root[x]);
        }
        
        return root[x];
    }
    
    /**
     * 合并两棵树
     *
     * @param x 待合并的树1
     * @param y 待合并的树2
     * @param w 边的权值
     */
    public void union(int x, int y, int w) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        
        // x 和 y 的根节点相同，即两者处于同一棵树中，联通分量相同
        if(rootX == rootY) {
            return;
        }
        // 如果 rootX 代表的树数量小于 rootY 所代表的树，那么就将
        // rootX 的树并到 rootY 的那棵树
        if(size[rootX] < size[rootY]) {
            root[rootX] = rootY;
            size[rootY]++;
        } else {
            root[rootY] = rootX;
            size[rootX]++;
        }
        
        System.out.println("加入边 (" + x + ", " + y + ")，其权值为：" + w);
    }
}