lca.c

最近公共祖先问题 问题描述：给定一棵树

#include<stdio.h>
#include<stdlib.h>
void main()
{ int i,j,n,n1,n2,m,k1,k2,*a,*b,*c;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d",&n);
  a=malloc((n+4)*sizeof(int));
  b=malloc((n+4)*sizeof(int));
  c=malloc((n+4)*sizeof(int));
  for(i=1;i<=n;i++)
  {scanf("%d",&n1);
   for(j=1;j<=n1;j++)
   {   scanf("%d",&n2);
	   a[n2]=i;
   }
  }
  a[1]=0;
scanf("%d",&m);
for(i=1;i<=m;i++)
{  scanf("%d %d",&b[1],&c[1]);
   if(b[1]==c[1])
	   printf("%d %d %d\n",b[1],b[1],b[1]);
   else
	  { k1=k2=1;
        while(b[k1]!=0)
		{b[k1+1]=a[b[k1]];k1++;}
        while(c[k2]!=0)
		{c[k2+1]=a[c[k2]];k2++;}
        do
		{k1--;k2--;}
        while(b[k1]==c[k2]);
       printf("%d %d %d\n",b[1],c[1],b[k1+1]);
   }


}

}