poj 2236 并查集.txt

ACM资料大集合

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

//POJ 2236 并查集
#define NMAX 1002
typedef struct point
{
	int fa;//父节点
	int sum;//跟该点在有效范围之内的点个数
	int conn[NMAX];//跟该点在有效范围内的点
	double x;//坐标
	double y;//坐标
	bool isok;//是否维修，可用
	int rank;//若该点为代表元素，则代表元素代表的这个集合有几个元素
}point;

point com[NMAX];

void init(int num,double d)
{
	int i,j,k;
	for(i=1;i<=num;i++)
	{
		com[i].fa=0;
		com[i].isok=false;
		com[i].rank=1;
		for(j=1,k=0;j<=num;j++)
		{
			if(i!=j && sqrt((com[i].x-com[j].x)*(com[i].x-com[j].x)+(com[i].y-com[j].y)*(com[i].y-com[j].y))<=d)
				com[i].conn[++k]=j;//com[j]在com[i]的有效范围内
		}
		com[i].sum=k;
//		printf("i=%d sum=%d\n",i,com[i].sum);
	}
}


int find(int x)
{	//查找x的代表元素
	int root=x,tt;
	while(com[root].fa!=0) 	root=com[root].fa;
	while(com[x].fa!=0) 
	{//压缩路径
		tt=com[x].fa;
		com[x].fa=root;
		x=tt;
	}
	return root;
}

void print()
{
	int i;
	for(i=1;i<=9;i++)
	{
		printf("(%d %d)",i,com[i].fa);
	}
	printf("\n");
}
void add(int a,int b)
{//把a,b的集合合在一起
	a=find(a);
	b=find(b);
//	print();
	if(a!=b)
	{//注意，如果a=b,将导致com[a].fa=a,接下去的find(a)会出现死循环
		if(com[a].rank<com[b].rank)
		{
			com[a].fa=b;
			com[b].rank+=com[a].rank;
		}
		else
		{
			com[b].fa=a;
			com[a].rank+=com[b].rank;
		}
	}
}

void repair(int x)
{	//修理x的同时，连接x有效范围内的点
	int i;
	com[x].isok=true;
	for(i=1;i<=com[x].sum;i++)
	{
		if(com[com[x].conn[i]].isok==true && com[x].conn[i]!=x) add(x,com[x].conn[i]);
	}
}

bool isconn(int a,int b)
{
	if(find(a)==find(b) && com[a].isok==true && com[b].isok==true) return true;
	else return false;
}

int main()
{
	int i,num,a,b;
	double d;
	char act[3];
	scanf("%d %lf",&num,&d);
	for(i=1;i<=num;i++)
	{
		scanf("%lf %lf",&com[i].x,&com[i].y);
	}
	init(num,d);
	while(scanf("%s",&act)!=EOF)
	{
		if(act[0]=='O') 
		{
			scanf("%d",&a);
			repair(a);
//			printf("O:  fa=%d sum=%d\n",com[a].fa,com[a].sum);
		}
		else 
		{
			scanf("%d %d",&a,&b);
			if(isconn(a,b)==true)
				printf("SUCCESS\n");
			else printf("FAIL\n");
		}
	}
	return 0;
}