本文主要是介绍poj 并查集 - 2236 Wireless Network，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集题目，并的意思就是将两个不同类别的集合合并到一起，类似于两棵树合并；查的意思就是找到这个点所属集合的根节点。基本上并查集题目都是在大体架构上面加一些东西即可。并查集代码模板在这里点击打开链接
现在n台之间有距离的电脑，只有距离小于d的才能连接，我们需要修复他们，让彼此之间可以互相连接。
这一次我们在并查集模板里面加入ranks数组用来记录该节点的修复情况，在union_set时，如果两台机器都修复了而且距离小于d，则合并。
#include <iostream>
#include<math.h>
using namespace std; const int MAXN = 1005;
int pa[MAXN];
int ranks[MAXN];
int x[MAXN];
int y[MAXN];
int n;
double d;void make_set(int size)
{int i;for(i=1;i<=size;i++){pa[i] = i;ranks[i]=0;x[i]=0;y[i]=0;}
} int find_set(int x)
{ if(x==pa[x]) return x; pa[x]=find_set(pa[x]); return pa[x];
} int dis(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
void union_set(int now)
{ int aa,bb,i;aa=find_set(now);for(i=1;i<=n;i++){if(ranks[i]&& find_set(i)!=aa && dis(x[now],y[now],x[i],y[i])<=d*d){bb=find_set(i); pa[bb]=aa; }}
} int main()
{ int i=0,T,j;char k;scanf("%d %lf",&n,&d);make_set(n);for(i=1;i<=n;i++){scanf("%d %d",&x[i],&y[i]);}while(~scanf("%c",&k)){if(k == 'S'){scanf("%d %d",&i,&j);if(find_set(i)!=find_set(j))printf("FAIL\n");else printf("SUCCESS\n");}else if(k=='O'){scanf("%d",&i);ranks[i]=1;union_set(i);}}return 0;
} 这篇关于poj 并查集 - 2236 Wireless Network的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
