首页 > 代码库 > POJ 2236 (简单并查集) Wireless Network

POJ 2236 (简单并查集) Wireless Network

2024-07-21 12:03:25   221人阅读

题意：

有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 LOCAL31         freopen("2236in.txt", "r", stdin);32     #endif33 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         else56         {57             scanf("%d%d", &a, &b);58             if(Find(a) == Find(b))59                 puts("SUCCESS");60             else61                 puts("FAIL");62         }63     }64 65     return 0;66 }
代码君

 

POJ 2236 (简单并查集) Wireless Network


联系
我们