POJ 1470 Closest Common Ancestors 解题报告

一、问题描述

 

二、解题思路

LCA问题，采用Tarjan算法。

参考http://blog.chinaunix.net/u3/105033/showart_2238641.html

 

三、代码

 

#include<iostream>
#include<vector>
using namespace std;
int T[905][905];//存储树
int n[905];//存储结果
bool color[905];//标记
int ancestor[905];//祖先
int p[905];//并查集使用
int r[905];//并查集使用
bool b[905];//用于查询根节点
vector<int> q[905];//存储查询
int N,NQ;//节点树和查询数
void MakeSet(int n)
{
    int i;
    for(i=1;i<=n;++i)
    {
        p[i]=i;
        r[i]=0;
    }
}
int FindSet(int x)
{
    if(x!=p[x])
    {
        p[x]=FindSet(p[x]);
    }
    return p[x];
}
void Link(int x,int y)
{
    if(r[x]>r[y])
        p[y]=x;
    else
        p[x]=y;
    if(r[x]==r[y])
        r[y]=r[y]+1;
}
void Union(int x,int y)
{
    int m=FindSet(x);
    int n=FindSet(y);
    if(m!=n)
        Link(m,n);
}
void LCA(int u)
{
    ancestor[FindSet(u)]=u;
    //ancestor[u]=u;
    int i=0;
    while(T[u][i]!=-1)
    {
        LCA(T[u][i]);
        Union(u,T[u][i]);
        ancestor[FindSet(u)]=u;
        i++;
    }
    color[u]=true;
    i=0;
    int size=q[u].size();
    for(i=0;i<size;++i)
    {
        int v=q[u][i];
        if(color[ v ]==true)
        {
            n[ancestor[FindSet(v)]]++;
        }
    }
}
int main()
{
    
    int i,j,t;
    int prt,cld;
    char ch;
    char cl,cr;
    int u,v;
    while(scanf("%d",&N)!=EOF)
    {
        memset(T,-1,sizeof(T));
        memset(color,0,sizeof(color));
        memset(n,0,sizeof(n));
        memset(b,0,sizeof(b));
        for(i=0;i<904;++i)
            q[i].clear();
        for(i=0;i<N;++i)
        {
            scanf("%d%c%c%d%c",&prt,&ch,&cl,&t,&cr);
            for(j=0;j<t;++j)
            {
                scanf("%d",&cld);
                T[prt][j]=cld;
                b[cld]=true;
            }
        }
        scanf("%d",&NQ);
        for(i=0;i<NQ;++i)
        {
            while(scanf("%c",&cl))
                if(cl=='(')
                    break;
                scanf("%d%d",&u,&v);
                q[u].push_back(v);
                q[v].push_back(u);
                while(scanf("%c",&cl))
                    if(cl==')')
                        break;
        }
        //查找根节点
        for(i=1;i<=N;++i)
        {
            if(b[i]==false)
                break;
        }
        MakeSet(N);
        LCA(i);
        for(i=1;i<=N;++i)
        {
            if(n[i]!=0)
                printf("%d:%d\n",i,n[i]);
        }
    }
    return 0;
}