并查集算法总结

xiaoxiao2021-03-01  45

算法总结:

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

题意描述:

给你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; }

 

转载请注明原文地址: https://www.6miu.com/read-4200321.html

最新回复(0)