裸的求LCA的题，今天看看了下，写下增加点认识。。。
有关tarjan的LCA的：
http://hi.baidu.com/niuniu_2006923/blog/item/3d57d0235ce7ae5a9922ed68.html
http://blog.csdn.net/apachecq/archive/2009/01/11/3753364.aspx
代码：
#include<iostream> #include<cstdio> #include<memory.h> #include<queue> using namespace std; const int MAX=905; struct node { int v,next; }g[MAX*MAX],query[MAX*MAX]; int parent[MAX],ancestor[MAX],cnt[MAX],adj[MAX],adj2[MAX],ind[MAX]; bool check[MAX]; int e,n,m,e2; int find(int x) { if(x!=parent[x]) parent[x]=find(parent[x]); return parent[x]; } void lca(int u) { int i,v; parent[u]=u; ancestor[find(u)]=u; for(i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; //cout<<v<<" "<<g[i].next<<endl; lca(v); parent[v]=u; ancestor[find(u)]=u; } check[u]=true; for(i=adj2[u];i!=-1;i=query[i].next) { v=query[i].v; //cout<<v<<endl; if(check[v]) cnt[ancestor[find(v)]]++; } } int main() { int i,j,k,a; while(scanf("%d",&n)!=EOF) { e=0; memset(cnt,0,sizeof(cnt)); memset(adj,-1,sizeof(adj)); memset(ind,0,sizeof(ind)); memset(check,false,sizeof(check)); for(i=1;i<=n;i++) parent[i]=i; for(a=1;a<=n;a++) { scanf(" %d:(%d)",&i,&k); //cout<<j<<" "<<k<<endl; while(k--) { scanf("%d",&j); g[e].v=j; g[e].next=adj[i]; adj[i]=e++; ind[j]++; } } scanf("%d",&m); e2=0; memset(adj2,-1,sizeof(adj2)); while(m--) { scanf(" (%d%d)",&i,&j); //cout<<i<<" "<<j<<endl; query[e2].v=j; query[e2].next=adj2[i]; adj2[i]=e2++; query[e2].v=i; query[e2].next=adj2[j]; adj2[j]=e2++; } //cout<<"yes"<<endl; for(i=1;i<=n;i++) if(ind[i]==0)//找树根 break; lca(i); for(i=1;i<=n;i++) { if(cnt[i]>0) printf("%d:%d/n",i,cnt[i]); } } return 0; }
