链接：http://poj.org/problem?id=2236
题意：
有一个计算机网络，n台计算机全部坏了，给你两种操作：
1.O x 修复第x台计算机
2.S x,y 判断两台计算机是否联通
联通的条件： 两台都修复好了，求距离小于d
思路：
数据很小，我们可以没修复一台就直接枚举已经修复的计算机找到距离小于d的，放到一个并查集里，查询的话直接查询是否再同一个并查集里就好了
实现代码：
//while(scanf("\n%c", &ope) != EOF)#include<iostream>#include<cstdio>using namespace std;const int M = 1e4+10;struct node{ ???int x,y,id;}a[M],b[M];int n,d;int f[M];int find(int x){ ???if(x == f[x]) return x; ???return f[x] = find(f[x]);}void mix(int x,int y){ ???int fx = find(x); ???int fy = find(y); ???if(fx != fy) f[fx] = fy;}bool check(node a,node b){ ???double num = (a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y); ???double num1 = d*d*1.0; ???if(num <= num1) return 1; ???return 0;}int main(){ ???char op;int k,l,r,cnt = 0; ???scanf("%d%d",&n,&d); ???for(int i = 1;i <= n;i ++) ???????scanf("%d%d",&a[i].x,&a[i].y),a[i].id = i; ???for(int i = 0;i <= n;i ++) ???????b[i].x = 0,b[i].y=0,b[i].id = 0,f[i]= i; ???while(scanf("\n%c", &op) != EOF){ ???????if(op == ‘O‘){ ???????????scanf("%d",&k); ???????????for(int i = 1;i <= cnt;i ++) ???????????????if(check(b[i],a[k])) ???????????????????mix(b[i].id,k); ???????????b[++cnt].x = a[k].x;b[cnt].y = a[k].y,b[cnt].id = a[k].id; ???????} ???????else{ ???????????scanf("%d%d",&l,&r); ???????????if(find(l) == find(r)) printf("SUCCESS\n"); ???????????else printf("FAIL\n"); ???????} ???}}poj 2236 Wireless Network ?(并查集）
原文地址：https://www.cnblogs.com/kls123/p/9563205.html