POJ 2236 (简单并查集) Wireless Network

浏览数：16 / 时间：2015年06月09日

题意：

有n个电脑坏掉了，分别给出他们的坐标

有两种操作，可以O x表示修好第x台电脑，可以 S x y表示x y是否连通

两台电脑的距离不超过d便可连通，两台电脑是连通的可以直接连通也可以间接通过第三台电脑连通

思路：

每次修好一台电脑都和前面已经修好的电脑比较一下如果距离小于d而且不在同一网络，便合并在一起即可

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 1000 + 10;
 8 struct Pos
 9 {
10     int x, y;
11 }pos[maxn];
12 
13 int p[maxn], o[maxn];
14 
15 int Find(int a)
16 {
17     return p[a] == a ? a : p[a] = Find(p[a]);
18 }
19 
20 void Union(int a, int b)
21 {
22     int pa = Find(a);
23     int pb = Find(b);
24     if(pa != pb)
25         p[pa] = pb;
26 }
27 
28 int main(void)
29 {
30     #ifdef LOCAL
31         freopen("2236in.txt", "r", stdin);
32     #endif
33 
34     int n, d, a, b, cnt = 0;
35     char cmd[10];
36     scanf("%d%d", &n, &d);
37     for(int i = 0; i <= n; ++i)    p[i] = i;
38     memset(o, false, sizeof(o));
39     for(int i = 1; i <= n; ++i)
40         scanf("%d%d", &pos[i].x, &pos[i].y);
41     while(scanf("%s", cmd) != EOF)
42     {
43         if(cmd[0] == ‘O‘)
44         {
45             scanf("%d", &a);
46             o[cnt++] = a;
47             for(int i = 0; i < cnt - 1; ++i)
48             {
49                 if((pos[a].x-pos[o[i]].x)*(pos[a].x-pos[o[i]].x) + (pos[a].y-pos[o[i]].y)*(pos[a].y-pos[o[i]].y) <= d * d)
50                 {
51                     Union(a, o[i]);
52                 }
53             }
54         }
55         else
56         {
57             scanf("%d%d", &a, &b);
58             if(Find(a) == Find(b))
59                 puts("SUCCESS");
60             else
61                 puts("FAIL");
62         }
63     }
64 
65     return 0;
66 }