poj 2236 Wireless Network (简单的并查集应用)
题目：http://poj.org/problem?id=2236
思路：每当修好一个电脑就找与其距离小于d的且已经修好的电脑与之合并即可。
代码：
#include<iostream>#include<queue>#include<cstring>using namespace std;const int MAXN=1005;bool hash[MAXN];int par[MAXN],rank[MAXN];int dx[MAXN],dy[MAXN];void initset(int n){for(int i=1;i<=n;i++){par[i]=i;rank[i]=0;}}int findpar(int x){if(par[x]==x) return x;return par[x]=findpar(par[x]);}void unionset(int x,int y){int fx=findpar(x),fy=findpar(y);if(fx==fy) return ;if(rank[fx]<rank[fy]){par[fx]=fy;}else{par[fy]=fx;if(rank[fx]==rank[fy]) rank[fx]++;}}int main(){int n,d;cin>>n>>d;initset(n);for(int i=1;i<=n;i++){cin>>dx[i]>>dy[i];}memset(hash,0,sizeof(hash));char op;while(cin>>op){if(op=='O'){int num;cin>>num;for(int i=1;i<=n;i++){int dis=(dx[i]-dx[num])*(dx[i]-dx[num])+(dy[i]-dy[num])*(dy[i]-dy[num]);if(hash[i] && dis<=d*d){unionset(num,i);//cout<<"unionset: "<<num<<" "<<i<<endl;}}hash[num]=1;}else if(op=='S'){int p,q;cin>>p>>q;int fp=findpar(p),fq=findpar(q);//cout<<"par: "<<fp<<" "<<fq<<endl;if(fp==fq) cout<<"SUCCESS"<<endl;else cout<<"FAIL"<<endl;}}return 0;}