pku 1330 Nearest Common Ancestors

题目链接：

http://poj.org/problem?id=1330

题目大意：

给定一棵树的边关系，注意是有向边，因为这个WA一发。然后N个顶点给出了N-1有向边，求一对点之间的最近公共祖先

思路：

裸的离线tarjan Lca即可，但注意是有向边，需要先找出根节点，数组标记。其次要注意前向星存的时候只存一条边即可

代码：

#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 10005;
struct node {
    int to,next;
} edges[maxn*2];
int n,head[maxn],f[maxn],vis[maxn],cnt,u,v,res,fir[maxn];
inline void addedge(int u, int v) {
    edges[cnt].to=v;
    edges[cnt].next=head[u];
    head[u]=cnt++;
}
inline void init() {
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    memset(fir,1,sizeof(fir));
    for(int i=1; i<=n; ++i) f[i]=i;
    cnt=0;
}
inline int Find(int x) {
    return x == f[x] ? x : f[x] = Find(f[x]);
}
inline void tarjan(int s) {
    vis[s]=1;
    int t;
    for(int i=head[s]; i!=-1; i=edges[i].next) {
        t=edges[i].to;
        if(!vis[t]) {
            tarjan(t);
            f[t]=s;
        }
    }
    if(s==u&&vis[v]) res=Find(v);
    else if(s==v&&vis[u]) res=Find(u);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,root;
    cin>>t;
    while(t--) {
        cin>>n;
        init();
        for(int i=1; i<n; ++i) {
            cin>>u>>v;
            fir[v]=0;
            addedge(u,v);
        }
        cin>>u>>v;
        for(int i=1; i<=n; ++i) {
            if(fir[i]) {
                root=i;
                break;
            }
        }
        tarjan(root);
        cout<<res<<endl;
    }
    return 0;
}

优质内容筛选与推荐>>
1、无奈的宇宙队、杯具的西梅
2、【Spark机器学习速成宝典】模型篇08支持向量机【SVM】（Python版）
3、计网基础-网络层服务
4、IIS安装
5、rpm 命令详解

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中