poj2236（并查集）

题目链接：http://poj.org/problem?id=2236

思路：

看到时间给到了10000MS，就可以直接套并查集板子了，不用特殊技巧。用结构体表示computer，元素x,y,s分别表示横纵坐标和状态（0表示未修好，1表示修好），root数组表示祖先数组，记住要初始化。还有输入字符时要么scanf(" %c",&c)（%c前加一个空格），要么用cin，因为scanf读字符不会吃掉换行，所以会读错，加个空格就行了（具体原因我也不知道，但这样用一直没错过）。详见代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 struct node{
 6     int x,y,s;
 7 }a[1005];
 8 
 9 int n,d,root[1005],p,q;
10 char c;
11 
12 int getr(int k){
13     if(root[k]==k) return k;
14     else return root[k]=getr(root[k]);
15 }
16 
17 bool check(int m,int n){
18     if((a[m].x-a[n].x)*(a[m].x-a[n].x)+(a[m].y-a[n].y)*(a[m].y-a[n].y)<=d*d)
19         return true;
20     else
21         return false;
22 }
23 
24 int main(){
25     scanf("%d%d",&n,&d);
26     for(int i=1;i<=n;++i)
27         scanf("%d%d",&a[i].x,&a[i].y),root[i]=i;
28     while(~scanf(" %c",&c)){
29         if(c=='O'){
30             scanf("%d",&p);
31             a[p].s=1;
32             for(int i=1;i<=n;++i)
33                 if(a[i].s==1&&check(p,i))
34                     root[getr(i)]=getr(p);
35         }
36         else{
37             scanf("%d%d",&p,&q);
38             if(getr(p)==getr(q))
39                 printf("SUCCESS
");
40             else 
41                 printf("FAIL
");
42         }
43     }
44     return 0;
45 }