poj1470——Closest Common Ancestors//LCA

果然A得辛苦，我想是用错模板了。囧，好累。http://www.cppblog.com/abilitytao/archive/2009/09/21/96886.html

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=906;
vector<int >p[maxn];
class node
{
public:
	int v,next;
};
node g[maxn*4];
int head[maxn],in[maxn],time[maxn],vis[maxn];
int f[maxn],r[maxn],ancestor[maxn];
int cnt,n,m;
void ini()
{
	int i;
	for(i=1;i<=n;i++)
	{
		f[i]=i;r[i]=1;
		in[i]=0;time[i]=0; head[i]=0;
		vis[i]=0;ancestor[i]=0;
		p[i].clear ();
	}
	cnt=0;
}
void read()
{
	int i,a,b,c,k;
	char ch;
	for(i=0;i<n;i++)
	{
		scanf("%d:(%d)",&a,&
			b);
		for(k=0;k<b;k++)
		{
			scanf("%d",&c);
			g[++cnt].v =c;
			g[cnt].next =head[a];
			head[a]=cnt;
			in[c]++;
		}
	}
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		while(getchar()!='(');
		scanf("%d %d)",&a,&b);
		p[a].push_back (b);
		p[b].push_back (a);
	}
}
int Find(int u)
{
	if(f[u]==u) return u;
	f[u]=Find(f[u]);
	return f[u];
}
void Union(int u,int v)
{
	int a=Find(u);
	int b=Find(v);
	if(a==b) return ;
	if(r[a]<r[b])
	{
		f[a]=b;r[b]+=r[a];
	}
	else 
	{
		f[b]=a;r[a]+=r[b];
	}
}
void LCA(int u)
{
	ancestor[u]=u;
	int i;
	for(i=head[u];i;i=g[i].next )
	{
		int v=g[i].v;
		LCA(v);
		Union(u,v);
		ancestor[Find(u)]=u;
	}
	vis[u]=1;
	int size=p[u].size();
	for(i=0;i<size;i++)
	{
		if(vis[p[u][i]]==1)
			time[ancestor[Find(p[u][i])]]++;
	}
}
int main()
{
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		ini();
		read();
		for(i=1;i<=n;i++)
			if(!in[i]) break;
		LCA(i);
		for(i=1;i<=n;i++)
			if(time[i])
				printf("%d:%d\n",i,time[i]);
	}
	return 0;
}