并查集的简单应用
一个集合中的电脑能够通信
每次修好一台电脑，都要进行合并集合
#include<iostream> #include<cmath> using namespace std; #define N 1005 #define eps 0.000001 int set[N],s[N]; struct point { int x,y; }; point p[N]; double dist(point p1,point p2) { return sqrt(((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))*1.0); } int find(int x) { int r,i,j; r=x; while(set[r]!=r) r=set[r]; i=x; while(i!=r) { j=set[i]; set[i]=r; i=j; } return r; } void merge(int x,int y) { if(x<y) set[y]=x; else set[x]=y; } void init(int n) { for(int i=1;i<=n;i++) { s[i]=0; set[i]=i; } } int main() { int n,d,i,x,y; char chr; scanf("%d%d",&n,&d); init(n); for(i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); getchar(); while(scanf("%c",&chr)!=EOF) { if(chr=='O') { scanf("%d",&x); s[x]=1; for(i=1;i<=n;i++) { if(i==x) continue; if(s[i]==1&&dist(p[i],p[x])<d+eps) merge(find(i),find(x)); } } if(chr=='S') { scanf("%d%d",&x,&y); if(x==y) { if(s[x]==1) printf("SUCCESS/n"); else printf("FAIL/n"); getchar(); continue; } if(find(x)==find(y)) printf("SUCCESS/n"); else printf("FAIL/n"); } getchar(); } return 0; }
