首页 > 其他 > 详细

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

时间:2014-01-22 21:59:50      阅读:407      评论:0      收藏:0      [点我收藏+]

Tarjan算法的详细介绍,请戳:

http://www.cnblogs.com/chenxiwenruo/p/3529533.html

 

bubuko.com,布布扣
#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=905;
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=0;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!=-1;k=edge[k].next){
        v=edge[k].to;
        LCA(v);
        uf.Union(u,v);
    }
    vis[u]=1;
    for(int i=0;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=0;
        memset(head,-1,sizeof(head));
        memset(indegree,0,sizeof(indegree));
        for(int i=0;i<maxn;i++)
            query[i].clear();
        for(int i=1;i<=n;i++){
            scanf("%d:(%d)",&u,&num);   //scanf的读取太强了
            for(int j=1;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=1;i<=n;i++)
            if(!indegree[i])
                root=i;
        memset(vis,0,sizeof(vis));
        memset(anc,0,sizeof(anc));
        uf.init();
        LCA(root);
        for(int i=1;i<=n;i++){
            if(anc[i]){
                printf("%d:%d\n",i,anc[i]);
            }
        }
    }
    return 0;
}
bubuko.com,布布扣

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

原文:http://www.cnblogs.com/chenxiwenruo/p/3529800.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!