?? poj 2236 并查集.txt
字號:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//POJ 2236 并查集
#define NMAX 1002
typedef struct point
{
int fa;//父節(jié)點
int sum;//跟該點在有效范圍之內(nèi)的點個數(shù)
int conn[NMAX];//跟該點在有效范圍內(nèi)的點
double x;//坐標(biāo)
double y;//坐標(biāo)
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]的有效范圍內(nè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,將導(dǎo)致com[a].fa=a,接下去的find(a)會出現(xiàn)死循環(huán)
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有效范圍內(nèi)的點
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;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -