Wireless Network（并查集）

（初学并查集，这道题算是把我做吐了，做了一晚上没做出来，最后看了题解发现如此简单）

题目链接 POJ2235 Wireless Network

由于有坐标，所以使用结构体存储坐标是比较好的选择，当然还要记录一下

每个节点的父节点。再题目输入完坐标后便开始进行修复与判断，于是在每一次的修复

过程中可以进行判断，那么判断标准是什么呢，当然首先不能是自己和自己比较，而且不能

和未修复好的电脑连线，那么该如何判断这台电脑有没有修好呢，于是再添加一个bool数组用来

判断这台电脑有没有修好，还有一个非常重要的条件，就是两台电脑的距离不能相差太远，这样的话

两台电脑也是无法连线的，综上考虑，就得出了四个条件。

那么在判断的时候，只需要判断两台电脑是否有公共祖先就可以了。

 1 #include <iostream>
 2 #include <vector>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 int fa[1110], n, d;
 7 bool vis[1010];
 8 struct Node{
 9     int x, y;
10 }node[1010];
11 int find(int x){
12     if(x != fa[x]) fa[x] = find(fa[x]);
13     return fa[x];
14 }
15 double len(int x1, int y1, int x2, int y2){
16     return double(sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)));
17 }
18 int main(){
19     cin >> n >> d;
20     for(int i = 1; i <= n; i ++){
21         cin >> node[i].x >> node[i].y;
22         fa[i] = i;
23     }
24     char op[5];
25     while(cin >> op){
26         int a, b, t;
27         if(op[0] == 'O'){
28             cin >> t;
29             vis[t] = true;
30             for(int i = 1; i <= n; i ++){
31                 if(vis[i] && i != t && find(t) != find(i)){
32                     if(len(node[i].x, node[i].y, node[t].x, node[t].y) <= d){ //四个限制条件
33                         fa[find(i)] = find(t);
34                     }
35                 }
36             }     
37         }else if(op[0] == 'S'){
38             cin >> a >> b;
39             if(find(a) == find(b))  //判断是否有公共祖先
40                 cout << "SUCCESS" << endl;
41             else
42                 cout << "FAIL" << endl;
43         }
44     }
45     return 0;   
46 }