| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 18013 | Accepted: 5774 |
Description
Input
Output
Sample Input
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1 5) (1 4) (4 2)
(2 3)
(1 3) (4 3)
Sample Output
2:1 5:5
有向图求LCA，注意输入的处理。
有向图只有一个树根,利用并查集求树根。无向图中可选任意一点作树根,在dfs是比有向图多一个条件，详情见代码。
#include"cstdio" #include"cstring" #include"vector" using namespace std; const int MAXN=1005; int V; vector<int> G[MAXN]; int par[MAXN]; void prep() { for(int i=0;i<=MAXN;i++) { par[i]=i; } } int fnd(int x) { if(par[x]==x) return x; return par[x]=fnd(par[x]); } void unite(int father,int son) { par[son]=fnd(father); } int fa[MAXN],dep[MAXN]; void dfs(int u,int father,int d) { fa[u]=father,dep[u]=d; for(int i=0;i<G[u].size();i++) dfs(G[u][i],u,d+1);//在无向图中 需要加上 if(G[u][i]!=father) } int lca[MAXN]; int LCA(int u,int v) { while(dep[u]>dep[v]) u=fa[u]; while(dep[v]>dep[u]) v=fa[v]; while(u!=v) { u=fa[u]; v=fa[v]; } return u; } int main() { while(scanf("%d",&V)!=EOF) { for(int i=0;i<=V;i++) G[i].clear(); prep(); memset(lca,0,sizeof(lca)); for(int i=0;i<V;i++) { int u,t; scanf("%d:(%d)",&u,&t); while(t--) { int v; scanf("%d",&v); G[u].push_back(v); unite(u,v); } } int root=fnd(1); dfs(root,-1,0); int Q; scanf("%d",&Q); while(true) { char ch=getchar(); if(ch==‘(‘) { int u,v; scanf("%d %d",&u,&v); int a=LCA(u,v); lca[a]++; Q--; getchar();//不能丢,有开就有闭 } if(Q==0) break; } for(int i=0;i<=V;i++) { if(lca[i]!=0) printf("%d:%d\n",i,lca[i]); } } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5171158.html