学步园

题目链接:   poj 1470

题目大意:   给出一棵树，然后有有限次查询(a,b)

                  每次查询节点a与节点b的最近公共祖先

                  输出节点作为最近公共祖先的次数

解题思路:   离线查询最近公共祖先

                  把每次查到的结果visit[ ]++，最后遍历一遍就行了

代码:

//Final   LCA离线算法求最近公共祖先
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 1000
vector<int> Hash[MAX],Qes[MAX];
int n,ansetor[MAX],visit[MAX],parent[MAX],fathernum[MAX],num[MAX];

void Init(int n)      //并查集初始化
{
    for(int i=1;i<=n;i++)
        parent[i]=i;
}

int Find(int x)        //并查集查找和压缩路径
{
    int s,j;
    s=x;
    while(x!=parent[x])
        x=parent[x];
    while(x!=s)
    {
        j=parent[s];
        parent[s]=x;
        s=j;
    }
    return x;
}

void Union(int r1,int r2)   //并查集合并
{
    int R1,R2;
    R1=Find(r1);
    R2=Find(r2);
    if(R1!=R2)
        parent[R1]=R2;
}

void LCA(int u)
{
    int i,size;
    size=Hash[u].size();
    ansetor[u]=u;
    for(i=0;i<size;i++)     //size()从0开始计算
    {
        LCA(Hash[u][i]);
        Union(u,Hash[u][i]);
        ansetor[Find(u)]=u;    //***可以是Find(u)或者Find(Hash[u][i])，因为已经合并了
    }
    visit[u]=1;
    size=Qes[u].size();
    for(i=0;i<size;i++)         //size()从0开始计算
    {
        if(visit[Qes[u][i]])    //如果需要查找的两个点其中一个点之前被访问过，
		{	                    //那么此时它的祖先就是它们的最近公共祖先
            num[ansetor[Find(Qes[u][i])]]++;   //***只能是Find(Qes[u][i])，因为此时u和Qes[u][i]并未合并
        }
    }
}

int main()
{
    int i,j,a,b,c,m,k=0;
    char ch,ch1;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            Hash[i].clear();
            Qes[i].clear();
        }
        k=0;
        Init(n);
        memset(visit,0,sizeof(visit));
        memset(ansetor,0,sizeof(ansetor));
        memset(num,0,sizeof(num));
        memset(fathernum,0,sizeof(fathernum));
        while(1)
        {
            scanf("%d%c",&a,&ch);
            if(ch!=':')
            {
                m=a;
                break;
            }
            scanf("%c%d%c",&ch1,&b,&ch1);
            for(j=1;j<=b;j++)
            {
                scanf("%d",&c);
                Hash[a].push_back(c);  //表示a是b的父亲
                fathernum[c]++;        //记录每个顶点父亲的个数
            }
            getchar();
        }
        while(scanf("%c",&ch)!=EOF)
        {
            if(ch=='(')
            {
                scanf("%d%d",&a,&b);
                getchar();
                k++;
                Qes[a].push_back(b);   //需要查找的两点
                Qes[b].push_back(a);   //需要查找的两点
                if(k>=m)
                {
                    break;
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(!fathernum[i])          //没有父亲结点的点既是整棵树的根节点
            {
                LCA(i);
                break;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(num[i])
               printf("%d:%d\n",i,num[i]);
        }
     }
    return 0;
}