POJ 1470 Closest Common Ancestors （最近公共祖先LCA 的离线算法Tarjan）

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <string>

#include <vector>

/*

AC

一开始读取数据的方式并不好，运行900多ms。

后来参照了别人的读取方式，600+ms。

*/

using namespace std;

const int maxn=;

int n,m;

int anc[maxn];  //记录以i为公共祖先的个数对

int indegree[maxn];  //记录入度

int vis[maxn];

vector<int> query[maxn];  //存储要查询的对

int head[maxn];

int tot;

struct Edge{

    int to,next;

}edge[maxn];

void add(int i,int j){

    edge[tot].next=head[i];

    edge[tot].to=j;

    head[i]=tot++;

}

//并查集

struct UF{

    int fa[maxn];

    void init(){

        for(int i=;i<=n;i++)

            fa[i]=i;

    }

    int find_root(int x){

        if(fa[x]!=x)

            fa[x]=find_root(fa[x]);

        return fa[x];

    }

    void Union(int u,int v){

        fa[v]=fa[u];

    }

}uf;

void LCA(int u){

    int v;

    for(int k=head[u];k!=-;k=edge[k].next){

        v=edge[k].to;

        LCA(v);

        uf.Union(u,v);

    }

    vis[u]=;

    for(int i=;i<query[u].size();i++){

        v=query[u][i];

        if(vis[v]){

            anc[uf.fa[uf.find_root(v)]]++;

        }

    }

}

int main()

{

    int u,v,num,root;

    char ch;

    while(scanf("%d",&n)!=EOF){

        tot=;

        memset(head,-,sizeof(head));

        memset(indegree,,sizeof(indegree));

        for(int i=;i<maxn;i++)

            query[i].clear();

        for(int i=;i<=n;i++){

            scanf("%d:(%d)",&u,&num);   //scanf的读取太强了

            for(int j=;j<=num;j++){

                scanf("%d",&v);

                add(u,v);

                indegree[v]++;

            }

        }

        scanf("%d",&m);

        while(m--){//这个读取方法比较妙

            while(getchar()!='(');

            scanf("%d%d",&u,&v);

            query[u].push_back(v);

            query[v].push_back(u);

        }

        while(getchar()!=')');  //别忘了读取最后的')'

        //寻找根节点

        for(int i=;i<=n;i++)

            if(!indegree[i])

                root=i;

        memset(vis,,sizeof(vis));

        memset(anc,,sizeof(anc));

        uf.init();

        LCA(root);

        for(int i=;i<=n;i++){

            if(anc[i]){

                printf("%d:%d\n",i,anc[i]);

            }

        }

    }

    return ;

}