POJ1861-Kruskal算法

之前也写过Kruskal算法，到今天才发现 原来以前的写错了。（也不能说完全错，只是效率好低）。

 

以前忽视的地方主要有两点，一是Kruskal算法，一般先对边从小到大排好序，然后从小到大区边。

这样的话，排完序以后就只要一个循环就可以走完。

二是 并查集的路径压缩，我以前对并查集合并是遍历所有的结点对两个集合合并，

而正确的做法应该是这样

int flindfather(int a)
{
if(a==father[a])
return a;
else 
return findfather(father[a]);
}

 

而其实我们还可以进行路径压缩，这才是并查集的核心所在

只要将上面的代码改写一行，就能起到很好的效果

int flindfather(int a)
{
if(a==father[a])
return a;
else 
return father[a]=findfather(father[a]);
}

 

下面是1861的代码

#include<iostream>
#include <algorithm>
using namespace std;
#define MAXSIZE 30010
#define INF 9000100
int n,m;
int father[MAXSIZE];//并查集
int head[MAXSIZE];
int next[MAXSIZE];
int e;

struct node{
	int u;
	int v;
	int w;
};
node edge[MAXSIZE];
node medge[MAXSIZE];
int num;
int ansmax,anstot;
//判断两点是否属于同一集合
int judge(int a,int b)
{
	if(father[a]==father[b])//同一集合
		return 1;
	return 0;
}
bool cmp(node &a,node &b)
{
	return a.w<b.w;
}
int findset(int a)
{
	if(a==father[a])
		return a;
	else 
		return father[a]=findset(father[a]);
}
void kruskal()
{
	sort(edge,edge+e,cmp);
	int i,j;
	num=0;
	ansmax=anstot=0;
	for(i=0;i<2*m;i++)
		father[i]=i; //初始时 每个元素属于不同的集合
	
	for(i=0;i<2*m;i++)
	{
		if(findset(edge[i].u)!=findset(edge[i].v))//如果不属于同一集合
		{
			ansmax=ansmax>edge[i].w?ansmax:edge[i].w;
			medge[num++]=edge[i];
			int tu=edge[i].u;//将所有与v一个集合的全部并入u的集合
			int tv=edge[i].v;
			father[findset(tv)]=findset(tu);
		}
		
	}

}
void addnode(int u,int v,int w)
{
	edge[e].u=u;
	edge[e].v=v;
	edge[e].w=w;
	next[e]=head[u];
	head[u]=e++;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		e=0;
		int t1=m;
		while(t1--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			addnode(a,b,c);
			addnode(b,a,c);
		}
		kruskal();
		printf("%d\n",ansmax);
		printf("%d\n",num);
		for(int i=0;i<num;i++)
			printf("%d %d\n",medge[i].u,medge[i].v);
	}
}