https://cn.vjudge.net/problem/POJ-2236
题意
有一个计算机网络的所有线路都坏了，网络中有n台计算机，现在你可以做两种操作，修理（O）和检测两台计算机是否连通（S），只有修理好的计算机才能连通。连通有个规则，两台计算机的距离不能超过给定的最大距离D（一开始会给你n台计算机的坐标）。检测的时候输出两台计算机是否能连通。
分析
注意审题。。只有修理好的才能算联通。于是把所有修理好的并一起就行了。
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <ctime>#include <vector>#include <queue>#include <map>#include <stack>#include <set>#include <bitset>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(a, b) memset(a, b, sizeof(a))#define pb push_back#define mp make_pair#define pii pair<int, int>#define eps 0.0000000001#define IOS ios::sync_with_stdio(0);cin.tie(0);#define random(a, b) rand()*rand()%(b-a+1)+a#define pi acos(-1)const ll INF = 0x3f3f3f3f3f3f3f3fll;const int inf = 0x3f3f3f3f;const int maxn = 1000 + 100;const int maxm = 200000 + 10;const int mod = 998244353;int fa[maxn];int n,d;pair<int,int> p[maxn];bool check(pair<int,int> x,pair<int,int> y){ ???return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second)<=d*d;}int find(int x){ ???return x==fa[x]?x:fa[x]=find(fa[x]);}void Union(int x,int y){ ???int fx=find(x),fy=find(y); ???if(fx!=fy) fa[fx]=fy;}int tmp[maxn];int main() {#ifdef LOCAL ???freopen("in.txt", "r", stdin);// ???freopen("output.txt", "w", stdout);#endif ???scanf("%d%d",&n,&d); ???for(int i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second),fa[i]=i; ???char op[3]; ???int x,y; ???int cnt=0; ???while(~scanf("%s",op)){ ???????if(op[0]==‘O‘){ ???????????scanf("%d",&x); ???????????for(int i=0;i<cnt;i++){ ???????????????if(tmp[i]!=x&&check(p[tmp[i]],p[x])){ ???????????????????Union(tmp[i],x); ???????????????} ???????????} ???????????tmp[cnt++]=x; ???????}else{ ???????????scanf("%d%d",&x,&y); ???????????int fx=find(x),fy=find(y); ???????????if(fx!=fy) puts("FAIL"); ???????????else puts("SUCCESS"); ???????} ???} ???return 0;}POJ - 2236 Wireless Network （并查集）
原文地址：https://www.cnblogs.com/fht-litost/p/9565908.html