poj1330Nearest Common Ancestors 1470 Closest Common Ancestors（LCA算法）

LCA思想：http://www.cnblogs.com/hujunzheng/p/3945885.html

在求解最近公共祖先為問題上，用到的是Tarjan的思想，從根結點開始形成一棵深搜樹，非常好的處理技巧就是在回溯到結點u的時候，u的子樹已經遍歷，這時候才把u結點放入合并集合中，
這樣u結點和所有u的子樹中的結點的最近公共祖先就是u了，u和還未遍歷的所有u的兄弟結點及子樹中的最近公共祖先就是u的父親結點。以此類推。。這樣我們在對樹深度遍歷的時候就很自然的將樹中的結點分成若干的集合，兩個集合中的所屬不同集合的任意一對頂點的公共祖先都是相同的，也就是說這兩個集合的最近公共最先只有一個。對于每個集合而言可以用并查集來優化，時間復雜度就大大降低了，為O(n + q)，n為總結點數，q為詢問結點對數。

/*
    題意很明顯，就是求LCA!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 10005
using namespace std;

int n;
int x, y;
vector<int>g[N];
int f[N];
int vis[N], cnt[N];
int ret;

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);
}

bool LCA(int u){
    vis[u]=1;
    f[u]=u;
    int len=g[u].size();
    
    if(u==x && vis[y]){
        ret=getFather(y);
        return true;
    }

    else if(u==y && vis[x]){
        ret=getFather(x);
        return true;
    }

    for(int i=0; i<len; ++i){
        int v=g[u][i];
        if(!vis[v]){
            if(LCA(v)) return true;
            f[v]=u;
        }
    }
    return false;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        memset(cnt, 0, sizeof(cnt));
        for(int i=1; i<n; ++i){
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            ++cnt[v];
        }
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &x, &y);
        for(int i=1; i<=n; ++i)
            if(cnt[i]==0){
                LCA(i);
                break;
            }
        printf("%d\n", ret);
        for(int i=1; i<=n; ++i)
            g[i].clear();
    }
    return 0;
}
 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 905
#define M 25000
using namespace std;

vector<int>g[N];
vector<int>p[M];
int cnt[N];
int f[N];
int vis[N];
int ans[N];

int n, m;

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);
}

void LCA(int u){
    f[u]=u;
    vis[u]=1;
    int len;
    
    len=p[u].size();
    for(int i=0; i<len; ++i){
        int v=p[u][i];
        if(vis[v])
              ++ans[getFather(v)];
    }
    
    len=g[u].size();
    for(int i=0; i<len; ++i){
           int v=g[u][i];
           if(!vis[v]){
            LCA(v);
            f[v]=u;   
        }
    }
}

int main(){
      while(scanf("%d", &n)!=EOF){
            memset(cnt, 0, sizeof(cnt));
          for(int i=1; i<=n; ++i){
                  vis[i]=0;
                  ans[i]=0;
                  int a, d, b;
                  char ch;
                  scanf("%d", &a);
                  while(scanf("%c", &ch) && ch!='(');
                  scanf("%d", &d);
                  while(scanf("%c", &ch) && ch!=')');
                  while(d--){
                   scanf("%d", &b);
                   ++cnt[b];
                   g[a].push_back(b);
                }
          }
          scanf("%d", &m);
          while(m--){
               char ch;
             while(scanf("%c", &ch) && ch!='(');
             int u, v;
             scanf("%d%d", &u, &v);
             p[u].push_back(v);
             p[v].push_back(u);
             while(scanf("%c", &ch) && ch!=')');
          }

          for(int i=1; i<=n; ++i)
             if(cnt[i]==0){
                LCA(i);
                break;
            }
         for(int i=1; i<=n; ++i)
            if(ans[i]!=0)
                printf("%d:%d\n", i, ans[i]);
                
         for(int i=1; i<=n; ++i)
            g[i].clear(), p[i].clear();
    }
    return 0;
}

?