POJ-2236 Wireless Network---并查集

题目链接：

题目大意：

给你N台电脑，从1-N。一个数字，表示两台计算机的最大通信距离，超过这个距离就无法进行通信。然后分别告诉这些电脑的坐标，接下来有两种操作，第一种O表示这点电脑修好，第二种S，表示测试这两台电脑能不能进行正常的通信

思路：

首先需要注意，只有某台电脑修好了，这台电脑才可以参加通信。

并查集的简单应用，对每次修好的电脑对其它已经修好的电脑遍历，如果距离小于等于最大通信距离就将他们合并。之后判断2台电脑是不是一个集合中就KO了

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<set>
 8 #include<map>
 9 #include<cmath>
10 using namespace std;
11 typedef pair<int, int> Pair;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 int T, n, m, d;
15 const int maxn = 1e3 + 10;
16 bool vis[maxn];//vis[i] = 1表示第i台电脑已经修好
17 int pa[maxn];
18 vector<int>G[maxn];
19 struct node
20 {
21     int x, y;
22 }a[maxn];
23 int dis(node a, node b)
24 {
25     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
26 }
27 void init()
28 {
29     for(int i = 1; i <= n; i++)scanf("%d%d", &a[i].x, &a[i].y);
30     for(int i = 1; i <= n; i++)
31     {
32         for(int j = i + 1; j <= n; j++)
33             if(dis(a[i], a[j]) <= d * d)G[i].push_back(j), G[j].push_back(i);
34     }
35     for(int i = 0; i <= n; i++)pa[i] = i;
36 }
37 int Find(int x)
38 {
39     return x == pa[x] ? x : pa[x] = Find(pa[x]);
40 }
41 int main()
42 {
43     cin >> n >> d;
44     init();
45     string s;
46     int x, y;
47     while(cin >> s)
48     {
49         if(s[0] == 'O')
50         {
51             scanf("%d", &x);
52             vis[x] = 1;
53             for(int i = 0; i < G[x].size(); i++)
54             {
55                 y = G[x][i];
56                 if(vis[y])
57                 {
58                     pa[Find(y)] = Find(x);
59                     //这里必须是pa[Find(y)] = Find(x)不能是pa[y] = x,因为是并查集根节点的更改
60                 }
61             }
62         }
63         else if(s[0] == 'S')
64         {
65             scanf("%d%d", &x, &y);
66             //cout<<Find(x)<<" "<<Find(y)<<endl;
67             if(Find(x) == Find(y))
68             {
69                 printf("SUCCESS
");
70             }
71             else printf("FAIL
");
72         }
73     }
74 }

POJ-2236 Wireless Network---并查集

相关推荐