poj2236和poj1611并查集问题

POJ 2236

问在计算机坏了，修复若干，问检测两台是否能连通

#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int N = 1005;struct Point{int x,y;};Point p[N];int repaired[N];int pre[N],rank[N];int dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}void Init(int n){for(int i=1;i<=n;i++){pre[i] = i;rank[i] = 1;}}int Find(int x){if(pre[x] != x)pre[x] = Find(pre[x]);return pre[x];}void Union(int x,int y){x = Find(x);y = Find(y);if(x == y) return;if(rank[x] >= rank[y]){pre[y] = x;rank[x] += rank[y];}else{pre[x] = y;rank[y] += rank[x];}}int main(){char ch[5];int n,d,x,y;scanf("%d%d",&n,&d);for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);int cnt = 0;Init(n);while(~scanf("%s",ch)){if(ch[0] == 'O'){scanf("%d",&x);for(int i=0;i<cnt;i++){if(dist(p[repaired[i]],p[x]) <= d*d)Union(repaired[i],x);}repaired[cnt++] = x;}else{scanf("%d%d",&x,&y);x = Find(x);y = Find(y);if(x == y) puts("SUCCESS");elseputs("FAIL");}}return 0;}

poj1611问是：学生0感染病毒，跟他一组的都得病，他可以交叉加入若干组，问一共的病的人数

并查集合并后，，遍历查询是否同一集合即可

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAX = 30010;int M,N;typedef struct UF{int par[MAX],rank[MAX];void init(){for (int i = 0; i <= MAX; ++i){par[i]=i;rank[i]=1;}};int find(int x){if(x!=par[x]){par[x]=find(par[x]);};return par[x];};int same(int x,int y){return find(x)==find(y);};void unions(int x,int y){int xx=find(x);int yy=find(y);if (xx==yy){return ;}if (rank[xx]<rank[yy]){par[xx]=yy;rank[yy]+=rank[xx];}if (rank[xx]>=rank[yy]){par[yy]=xx;rank[xx]+=rank[yy];}};}UF;UF uf;int main(int argc, char const *argv[]){while(scanf("%d%d",&N,&M)&&M&&N){uf.init();for (int i = 0; i < M; ++i){int num,fir;scanf("%d",&num);scanf("%d",&fir);for (int j = 1; j < num ; ++j){int tmp;scanf("%d",&tmp);uf.unions(fir,tmp);}}int sum=1;for (int i = 1; i < N; ++i){if (uf.same(0,i)){sum++;}}printf("%d\n",sum);}return 0;}

在泪水中浸泡过的微笑最灿烂，从迷惘中走出来的灵魂最清醒。