并查集算法总结

算法总结：

该算法我理解的就是找祖先，然后合并祖先，使他们有共同祖先，在找共同祖先的时候可以用靠左原则，也就是都服从于左边的为祖先

题意描述：

给你n个人编号为1到n和m条信息，求他们的父亲和祖先

样例输入：

5 4

1 3

2 3

1 2

4 5

样例输出：

2 2 1 4 4

2 2 2 4 4

程序代码：

#include<stdio.h> #include<string.h> int getf(int u); void merge(int u,int v); int f[110]; int main() { int n,m,i,j,k,a,b; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); merge(a,b); } for(i=1;i<=n;i++) printf("%d ",f[i]);//输出父亲 printf("\n"); for(i=1;i<=n;i++) printf("%d ",getf(i));//输出祖先 printf("\n"); } return 0; } int getf(int u)//找祖先 { if(u==f[u]) return u; f[u]=getf(f[u]); return f[u]; } void merge(int u,int v)//合并祖先 { u=getf(u); v=getf(v); if(u!=v) f[v]=u; }