Nearest Common Ancestors-Tarjan

update@2011-08-21

//主要代码如下
vector<int> tree[10001];
int is_root[10001];
int father[10001];
int visited[10001];

int FindSet(int x){
    return x == father[x]?x:(father[x] = FindSet(father[x]));
}
void UnionSet(int x,int y){
    father[FindSet(y)] = FindSet(x);
}
void Tarjan_LCA(int u,int a,int b){
    //tarjan算法的精髓是深搜 回溯 合并的过程
    //多理解这个过程
    int size_tree = tree[u].size();
    for(int i = 0;i < size_tree;i++){
        Tarjan_LCA(tree[u][i],a,b);
        UnionSet(u,tree[u][i]);
    }
    visited[u] = true;
    if(u == a && visited[b] == true)
        printf("%d\n",FindSet(b));
    if(u == b && visited[a] == true){
        printf("%d\n",FindSet(a));
    }
}
void init(int n){
    for(int i = 1;i <= n;i++){
        tree[i].clear();    father[i] = i;
        visited[i] = false; is_root[i] = true;
        //初始化为true之后如果它作为了子节点就赋值为false 最后剩下的就是根节点
    }
}
int findRoot(int n){
    for(int i = 1;i <= n;i++){
        if(is_root[i] == 1) return i;
    }
    return 0;
}
//main函数中的主要部分
init(n);
for(i = 1;i < n;i++){
    scanf("%d%d",&a,&b);
    tree[a].push_back(b);
    is_root[b] = 0;//作为子节点
}
scanf("%d%d",&a,&b);
Tarjan_LCA(findRoot(n),a,b);



题目链接:Nearest Common Ancestors
基础的LCA问题,用的tarjan算法,弄清深搜回溯合并的过程就能理解了,理解这个之前应该先熟悉并查集,再看这里 ,然后动手刷刷题.