首页 > 代码库 > poj 1470 Closest Common Ancestors tarjan求lca和树的孩子兄弟表示
poj 1470 Closest Common Ancestors tarjan求lca和树的孩子兄弟表示
题意:
给一棵树和若干查询点对,求这些点对的lca。
分析:
tarjan求lca的模板题,树还是用孩子兄弟表示法比较简洁。
代码:
//poj 1470 //sepNINE #include <iostream> #include <vector> using namespace std; const int maxN=1024; int n,u,v,t,m,x,y;; int par[maxN],son[maxN],bro[maxN],f[maxN],cnt[maxN],vis[maxN]; vector<int> query[maxN]; int find(int u) { return f[u]==u?u:f[u]=find(f[u]); } void tarjan(int root) { int i; f[root]=root; vis[root]=1; for(i=query[root].size()-1;i>=0;--i){ int p=query[root][i]; if(vis[p]==1) ++cnt[find(p)]; } int s=son[root]; while(s){ tarjan(s); f[s]=root; s=bro[s]; } } int main() { char ch1[4],ch2[4],ch3[4]; int i; while(scanf("%d",&n)==1){ memset(par,0,sizeof(par)); memset(son,0,sizeof(son)); memset(bro,0,sizeof(bro)); for(i=1;i<=n;++i) query[i].clear(); for(i=1;i<=n;++i){ scanf("%d%1s%1s%d%1s",&u,ch1,ch2,&t,&ch3); while(t--){ scanf("%d",&v); par[v]=1; bro[v]=son[u]; son[u]=v; } } for(i=1;i<=n;++i) if(par[i]==0) break; scanf("%d",&m); while(m--){ scanf("%1s%d%d%1s",ch1,&x,&y,ch2); query[x].push_back(y); if(x!=y) query[y].push_back(x); } memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); tarjan(i); for(i=1;i<=n;++i) if(cnt[i]) printf("%d:%d\n",i,cnt[i]); } return 0; }
poj 1470 Closest Common Ancestors tarjan求lca和树的孩子兄弟表示
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。