poj1470——Closest Common Ancestors//LCA

44424742

果然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;}