算法总结:
该算法我理解的就是找祖先,然后合并祖先,使他们有共同祖先,在找共同祖先的时候可以用靠左原则,也就是都服从于左边的为祖先
题意描述:
给你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; }