POJ 2236 并查集

本文主要是介绍POJ 2236 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Time Limit: 10000MS.........

直接暴力查找。。连通的用并查集处理一下就行了

#include "stdio.h"
#include "string.h"
#include "math.h"
#include "stdlib.h"struct comp
{double x,y;
} point[1010];int n;
double d;
int hash[1010];
double dis[1010][1010];
int fa[1010];double make_dis(int a,int b)
{return sqrt(  (point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));
}int find(int x)
{if (x!=fa[x])fa[x]=find(fa[x]);return fa[x];
}void repair(int x)
{int i,a,b;hash[x]=1;for (i=1;i<=n;i++)if (i!=x && hash[i]==1 && dis[x][i]-d<1e-10){a=find(x);b=find(i);if (a!=b)fa[a]=b;}
}			int main()
{int i,x,y,j;char ch;scanf("%d%lf",&n,&d);for (i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);for (i=1;i<=n;i++)for (j=i;j<=n;j++)if (i==j)dis[i][j]=dis[j][i]=0;else dis[i][j]=dis[j][i]=make_dis(i,j);getchar();memset(hash,0,sizeof(hash));for (i=1;i<=n;i++)fa[i]=i;while (scanf("%c",&ch)!=EOF){if (ch=='O') {scanf("%d",&x);repair(x);}else {scanf("%d%d",&x,&y);if (find(fa[x])==find(fa[y])) printf("SUCCESS\n");else printf("FAIL\n");}getchar();}return 0;
}

这篇关于POJ 2236 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---