/*kruskal算法思想：每次選擇圖中最小邊權的邊，如果邊兩端的頂點在不同的連通塊中，就把這條邊加入最小生成樹中。kruskal偽代碼如下：int kruskal(){	令最小生成樹的邊權之和為ans、最小生成樹的當前邊數(shù)Num_Edge;	將所有邊按邊權從小到大排序；	for(從小到大枚舉所有邊)	{		if(當前測試邊的兩個端點在不同的連通塊中)		{			將該測試邊加入最小生成樹中；			ans+=測試邊的邊權；			最小生成樹的當前邊數(shù)Num_Edge加1；			當邊數(shù)Num_Edge等于頂點數(shù)減1時結束循環(huán)；		}	}	return ans;}*///kruskal算法應用實現(xiàn)代碼#include<cstdio>#include<algorithm>using namespace std;const int MAXV = 110;const int MAXE = 10010;//邊集定義部分struct edge{	int u, v;//邊的兩個端點編號	int cost;//邊權}E[MAXE];//最多有MAXE邊bool cmp(edge a, edge b){	return a.cost < b.cost;}//并查集部分int father[MAXV];//并查集數(shù)組/*int findFather(int x)//并查集查詢函數(shù){	int a = x;	while (x != father[x])	{		x = father[x];	}	//路徑壓縮	while (a != father[a])	{		int z = a;		a = father[a];		father[z] = x;	}	return x;}*/int findFather(int x)//遞歸版{	if (x == father[x])		return x;	else	{		int f = findFather(father[x]);		father[x] = f;		return f;	}}//kruskal部分，返回最小生成樹的邊權之和，參數(shù)n為頂點個數(shù)，m為圖的邊數(shù)int kruskal(int n, int m){	//ans為所求邊權之和，Num_Edge為當前生成樹的邊數(shù)	int ans = 0, Num_Edge = 0;	for (int i = 0; i < n; i++)//頂點范圍是[0,n-1]	{		father[i] = i;//并查集初始化	}	sort(E, E + m, cmp);//所有邊按邊權從小到大排序	for (int i = 0; i < m; i++)//枚舉所有邊	{		int faU = findFather(E[i].u);//查詢測試邊兩個端點所在集合的根結點		int faV = findFather(E[i].v);		if (faU != faV)//如果不在一個集合中		{			father[faU] = faV;//合并集合(即把測試邊加入最小生成樹中)			ans += E[i].cost;//邊權之和增加測試邊的邊權			Num_Edge++;//當前生成樹的邊數(shù)加1			if (Num_Edge == n - 1)break;//邊數(shù)等于頂點數(shù)減1時結束算法		}	}	if (Num_Edge != n - 1)return -1;//無法連通時返回-1	else return ans;//返回最小生成樹的邊權之和}int main(){	int n, m;	scanf("%d%d", &n, &m);//頂點數(shù)，邊數(shù)	for (int i = 0; i < m; i++)	{		scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);//兩個端點的編號、邊權	}	int ans = kruskal(n, m);//kruskal算法入口	PRintf("%d/n", ans);	return 0;}