poj 1470--tarjan--LCA

/*
    ，       ，     LCA,    LCA  ，    
*/
#include<stdio.h>
#include<string.h>
const int max=1000;
struct Heap{//    blog    ，   
    int head[max];
    int key[max*max];
    int next[max*max];
    int pos;
    Heap(){clear();}
    void clear(){memset(head,-1,sizeof(head));pos=0;}
    void add(int s,int e)
    {
        key[pos]=e;
        next[pos]=head[s];
        head[s]=pos;
        pos++;
    }
};
Heap heap,query;
int vis[max],in[max],ans[max],f[max];
int get(int i)
{
	if(f[i]==i)
		return i;
	return f[i]=get(f[i]);
}
void tarjan(int k)//
{
	int i;
	f[k]=k;//     ，           ，
	for(i=heap.head[k];i!=-1;i=heap.next[i])
	{
		tarjan(heap.key[i]);//tarjan    
		f[heap.key[i]]=k;//      ，        
	}

	vis[k]=1;//     

	for(i=query.head[k];i!=-1;i=query.next[i])//       ，          
	{
		if(vis[query.key[i]])
			ans[get(query.key[i])]++;
	}
}
int main()
{
	int n,i,a,nn,j,b,nq;
	while(~scanf("%d",&n))
	{
		memset(vis,0,sizeof(vis));
		memset(in,0,sizeof(in));
		memset(ans,0,sizeof(ans));
		heap.clear();//      
		query.clear();
		for(i=1;i<=n;i++)
		{
			scanf("%d:(%d)",&a,&nn);
			for(j=1;j<=nn;j++)
			{
				scanf("%d",&b);
				heap.add(a,b);
				in[b]++;
			}
		}
		scanf("%d",&nq);
		for(i=1;i<=nq;i++)
		{
			while(getchar()!='(');
			scanf("%d%d",&a,&b);
			query.add(a,b);//                  (  tarjan()，       ，          )，      ，
			query.add(b,a);//         （       ，          ）    ,                  ，         
			while(getchar()!=')');
		}


		for(i=1;i<=n;i++)
			if(!in[i])
			{
				tarjan(i);
				break;
			}
		for(i=1;i<=n;i++)
			if(ans[i])
				printf("%d:%d
",i,ans[i]);
	}
	return 0;
}