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;class node{public:int v,next;};node g;int head,in,time,vis;int f,r,ancestor;int cnt,n,m;void ini(){int i;for(i=1;i<=n;i++){f=i;r=1;in=0;time=0; head=0;vis=0;ancestor=0;p.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.next =head;head=cnt;in++;}}scanf("%d",&m);for(i=0;i<m;i++){while(getchar()!='(');scanf("%d %d)",&a,&b);p.push_back (b);p.push_back (a);}}int Find(int u){if(f==u) return u;f=Find(f);return f;}void Union(int u,int v){int a=Find(u);int b=Find(v);if(a==b) return ;if(r<r){f=b;r+=r;}else {f=a;r+=r;}}void LCA(int u){ancestor=u;int i;for(i=head;i;i=g.next ){int v=g.v;LCA(v);Union(u,v);ancestor=u;}vis=1;int size=p.size();for(i=0;i<size;i++){if(vis]==1)time)]]++;}}int main(){int i;while(scanf("%d",&n)!=EOF){ini();read();for(i=1;i<=n;i++)if(!in) break;LCA(i);for(i=1;i<=n;i++)if(time)printf("%d:%d\n",i,time);}return 0;}
页:
[1]