考研数据结构——每日一题[最小生成树Kruskal]

Kruskal算法 O(mlogm)

贪心按边权从小到大加入边，并查集判断点是否在集合中，不在的加入并查集

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510 	, 	M = 100010;
int n,m;

struct Edge
{
	int a,b,c; //a->b : value = c 
	bool operator< (const Edge &t)const 
	{
		return c < t.c;
	}
}e[M];
int p[N];

int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d%d",&n,&m);//n个点m条边 
	for(int i = 0;i < m;i ++)
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);//输入每条边
	sort(e , e + m);//先排好序按权值大小（重载小于号） [贪心思想每次选取未加入的点的最小边权] 
	
	for(int i = 1;i <= n;i++) p[i] = i;//初始化并查集，维护点的集合 
			
	int res = 0,cnt = n; //统计n个点之间的最小边权和（最小生成树）  [若不是点都联通，则不可能]
	for(int i = 0;i < m;i++)    //枚举所有边	 
	{
		int  a = e[i].a ,b = e[i].b , c =  e[i].c;//简化赋值 
		if(find(a) != find(b))//加入集合过程计算最小生成树的值 
		{
			res += c; 
			cnt --;
			p[find(a)] = find(b);
		}
	}

	if(cnt > 1) puts("impossple");//无法生成最小生成树 
	else printf("%d\n",res); 
	
	return 0;
}