poj 2236 并查集

题意：一张图上分布着n台坏了的电脑，并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网，也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x，给出操作“S x y”，请你判断x和y在此时有没有连接上。

链接：点我

水并查集，注意节点从1开始

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 #define cl(a) memset(a,0,sizeof(a))
13 #define ts printf("*****
");
14 const int MAXN=1005;
15 int n,m,tt;
16 int f[MAXN];
17 bool g[MAXN][MAXN];
18 struct node
19 {
20     double x,y;
21     void in()
22     {
23         scanf("%lf%lf",&x,&y);
24     }
25 }nn[MAXN];
26 double dis(node a,node b)
27 {
28     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
29 }
30 int find(int x)
31 {
32     if(f[x]==-1)return x;
33     return f[x]=find(f[x]);
34 }
35 void bing(int u,int v)
36 {
37     int t1=find(u),t2=find(v);
38     if(t1!=t2)f[t1]=t2;
39 }
40 bool vis[MAXN];
41 int main()
42 {
43     int i,j,k;
44     #ifndef ONLINE_JUDGE
45     freopen("1.in","r",stdin);
46     #endif
47     memset(g,false,sizeof(g));
48     memset(vis,false,sizeof(vis));
49     memset(f,-1,sizeof(f));
50     int d,u,v;
51     scanf("%d%d",&n,&d);
52     for(i=1;i<=n;i++)
53         nn[i].in();
54     for(i=1;i<=n;i++)
55     {
56         for(j=1;j<=n;j++)
57         {
58             if(dis(nn[i],nn[j])<=d+eps)
59             {
60                 g[i][j]=1;
61             }
62         }
63     }
64     char s[8];
65     while(scanf("%s",&s)==1)
66     {
67         if(s[0]=='O')
68         {
69             scanf("%d",&u);
70             if(!vis[u])
71             {
72                 for(int i=1;i<=n;i++)
73                   if(vis[i]&&g[u][i])
74                     bing(u,i);
75                 vis[u]=true;
76             }
77         }
78         else
79         {
80             scanf("%d%d",&u,&v);
81             if(find(u)==find(v))printf("SUCCESS
");
82             else printf("FAIL
");
83         }
84     }
85 }