SP14932 LCA - Lowest Common Ancestor

柔情只为你懂 2021-12-23 23:59 166阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node1{
        int nxt;
        int to;
    }tree[maxn*2];
    struct node2{
        int nxt;
        int to;
        int LCA;
    }qtree[maxn*2];
    int head1[maxn],cnt1;
    void add1(int x,int y){
        tree[++cnt1].nxt=head1[x];
        tree[cnt1].to=y;
        head1[x]=cnt1;
    }
    int head2[maxn],cnt2;
    void add2(int x,int y){
        qtree[++cnt2].nxt=head2[x];
        qtree[cnt2].to=y;
        head2[x]=cnt2;
    }
    int vis[maxn];
    int fa[maxn];
    int fifa(int x){
        if(x!=fa[x]) return fa[x]=fifa(fa[x]);
    }
    void Tarjan(int x){
        vis[x]=1;
        for(int i=head1[x];i;i=tree[i].nxt){
            int v=tree[i].to;
            if(vis[v]) continue;
            Tarjan(v);
            fa[v]=x;
        }
        for(int i=head2[x];i;i=qtree[i].nxt){
            int v=qtree[i].to;
            if(vis[v]){
                qtree[i].LCA=fifa(v);
                if(i%2){
                    qtree[i+1].LCA=qtree[i].LCA;
                }
                else qtree[i-1].LCA=qtree[i].LCA;
            }
        }
    }
    int T,ljb,n,m,k,x,y;
    int main(){
        scanf("%d",&T);
        while(T--){
            ljb++;
            scanf("%d",&n);
            memset(head1,0,sizeof(head1));
            memset(head2,0,sizeof(head2));
            cnt1=0,cnt2=0;
            memset(qtree,0,sizeof(qtree));
            memset(tree,0,sizeof(tree));
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++) fa[i]=i;
            for(int i=1;i<=n;i++){
                scanf("%d",&m);
                for(int j=1;j<=m;j++){
                    scanf("%d",&x);
                    add1(x,i);
                    add1(i,x);
                }
            }
            scanf("%d",&k);
            for(int i=1;i<=k;i++){
                scanf("%d%d",&x,&y);
                add2(x,y);
                add2(y,x);
            }
            Tarjan(1);
            printf("Case %d:\n",ljb);
            for(int i=1;i<=k;i++){
                printf("%d\n",qtree[i*2].LCA);
            }
        }
        return 0;
    }

Tarjan求LCA，打起来真的爽

转载于:https://www.cnblogs.com/LJB666/p/11025434.html