NUAA ACM OJ源码

				#include 
				#include 
				#include 
				
				//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					{
						com[i].fa=0;
						com[i].isok=false;
						com[i].rank=1;
						for(j=1,k=0;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))								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					{
						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[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					{
						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					{
						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;
				}