学步园

LCA 模板 + poj 1330

#include<iostream>
#include<vector>
using namespace std;

const int MAX=10001;
int f[MAX]; //每个节点所属的集合
int r[MAX];  //r是rank(秩) 合并
int indegree[MAX];//保存每个节点的入度
int visit[MAX];//只有1和0，表示某节点的Id是否已处理完毕
vector<int> tree[MAX],Qes[MAX];//树，查询
int ancestor[MAX]; //祖先集合


void init(int n)
{
    for(int i=1;i<=n;i++)
    {

        r[i]=1; //每个节点的秩初始为1，
        f[i]=i;  //每个节点的父节点初始为自身
        indegree[i]=0;
        visit[i]=0;
        ancestor[i]=0; //祖先为0
        tree[i].clear();
        Qes[i].clear();
    }

}

int find(int n) //查找n节点所在的集合
{
    if(f[n]==n)
        return n;
    else
        f[n]=find(f[n]);
    return f[n];
}//查找函数，并压缩路径

int Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return 0;
    //相等的话,x向y合并
    else if(r[a]<=r[b])
    {
        f[a]=b;       //两个秩相等，合并到左边的秩
        r[b]+=r[a];  //小的秩合并向大的秩
    }
    else
    {
        f[b]=a;
        r[a]+=r[b];
    }
    return 1;

}//合并函数，如果属于同一分支则返回0，成功合并返回1


void LCA(int u)
{
    ancestor[u]=u;
    int size = tree[u].size();
    for(int i=0;i<size;i++)
    {
        LCA(tree[u][i]);
        Union(u,tree[u][i]);
        ancestor[find(u)]=u;  //让u的父节点为u,因为回溯操作，一定保证集合的祖先是最近祖先，
    }
    visit[u]=1;
    size = Qes[u].size();
    for(int i=0;i<size;i++)
    {
        //如果已经访问了问题节点,就可以返回结果了.
        if(visit[Qes[u][i]]==1)
        {
            cout<<ancestor[find(Qes[u][i])]<<endl;
            return;
        }
    }
}


int main()
{
    int cnt;
    int n;
    cin>>cnt;
    while(cnt--)
    {
        cin>>n;;
        init(n);
        int s,t;
        for(int i=1;i<n;i++)
        {
            cin>>s>>t;
            tree[s].push_back(t);
            indegree[t]++;
        }
        //这里可以输入多组询问
        cin>>s>>t;
        //相当于询问两次
        Qes[s].push_back(t);
        Qes[t].push_back(s);
        for(int i=1;i<=n;i++)
        {
            //寻找根节点
            if(indegree[i]==0)
            {
                LCA(i);
                break;
            }
        }
    }
    return 0;
}

算法步骤：
1 由根节点开始，进行深度优先遍历，遍历到叶子节点，置其对应的visit[i] = 1;
2 将父节点与子节点进行合并（将他们置于同一个集合，详细看union代码），
然后，将集合的祖先置为当前节点。（要注意回溯的过程，一定是保证高层次的）
3 询问查询，即qes[u][i]，u是查询节点之一（正好是当前节点），
i是另一个查询节点，如果i此时已被处理完毕，
说明i在u的左边，那么i所在集合（并不是像有些文章说的i的父节点，这概念不正确）的祖先一定u，
i的最近共同祖先（如果u，i在同一子树，则很好理解，如果u，i在不同子树，
那么i所在集合的祖先也是u的祖先（注意回溯，上升，下降））；
如果i此时未被处理，说明i在u的右边，对于u，i的询问只能跳过，但是对i，u的询问可以处理。
这个是两个节点共同祖先的查询，多个的话就用前两个的查询结果与下一个组成一个查询，依次类推。