LCA最近の公的祖先(メモ、テンプレート)

lcaを求める方法は大体3種類ある:1.dfs+RMQ(線分ツリーSTテーブルとか)オンライン2.倍増オンライン3.tarjanオフライン
ps:オフライン:すべてのクエリーが全入力後に一度解決オンライン:次のテンプレートを出力するクエリーがあります.洛谷P 3379【テンプレート】最近の共通祖先(LCA)

1.まずdfsから求める

1>dfs遍歴時に通過するすべてのノードの位置2>各ノードが初めて現れる位置3>各ノードの深さクエリ時に先に2つのノードの位置を取り出してこの2つの位置間の深さが最も小さいノードを求めるこのノードがlca codeである.

//By Menteur_Hxy 2068ms
#include
#include
#include
using namespace std;

const int INF=0x3f3f3f3f;
const int MAX=500110;

int n,qu,root,cnt;
int head[MAX],ver[MAX*2],first[MAX],log[MAX*2],deep[MAX],f[MAX*2][21];

struct edges{
    int to,next;
}edge[MAX*2+5];

void add(int x,int y) {
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    head[x]=cnt;
}

void dfs(int u,int pre) {
    ver[++cnt]=u;
    first[u]=cnt;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=pre) {
            deep[v]=deep[u]+1;
            dfs(v,u);
            ver[++cnt]=u;
        }
    }
}

void ST() {
    for(int i=1;i<=cnt;i++) f[i][0]=ver[i];
    log[1]=0,log[2]=1;
    for(int i=3;i<=cnt;i++) {
        log[i]=log[i-1];
        if(1<<log[i-1]+1==i) log[i]++;
    }
    int k=log[cnt];
    for(int j=1;j<=k;j++)
        for(int i=1;i+(1<1<=cnt;i++) {// !!!
            if(deep[f[i][j-1]]1<1)][j-1]])
                f[i][j]=f[i][j-1];
            else f[i][j]=f[i+(1<1)][j-1];
        }

}

int RMQ(int l,int r) {
    int k=log[r-l+1];
//  cout<
    if(deep[f[l][k]]1<1][k]])
        return f[l][k];
    else return f[r-(1<1][k];
//  return min(f[l][k],f[r-1<
}

int ask(int x,int y) {
    x=first[x];y=first[y];
    if(x>y) swap(x,y);
    return RMQ(x,y);
}

int main() {
    scanf("%d %d %d",&n,&qu,&root); 
    for(int i=1;iint a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    cnt=0;
    dfs(root,-1);
//  for(int i=1;i<=cnt;i++) cout<
//  cout<
    ST();
    for(int i=1;i<=qu;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d
",ask(a,b));
    }
    return 0;
}

2.倍増

同様にdfsが必要であるが、深さと各ノードの父親が現在f[i][j]を設定してiの2番目の^j個の祖先(eg:f[i][0]をiの父親とする)を表すので、f[i][j]=f[f[i][j-1]][j-1](iの2番目の^j-1個の祖先がiの2^j-1個の祖先である)が両ノードを問い合わせる場合、まず深さの大きいノードを別のノードと同じ深さになるまで上へ移動し、このとき2つのノードが同じかどうかを判断するには、大きいものから小さいものまで列挙して2つのノードの父親が同じになるまでジャンプしようとします.このとき、父はlcaです.
code:

//By Menteur_Hxy 1860ms
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int MAX=500010;

int n,qu,root,cnt;
int head[MAX],deep[MAX],f[MAX][20];
/*
f[i][j] i 2^j 
*/
struct edges{
    int to,next;
}edge[MAX*2];

void add(int x,int y) {
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}

void dfs_bz(int cur) {
    for(int i=head[cur];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=f[cur][0]) { // ！！！ 
//          cout<
            f[v][0]=cur;
            deep[v]=deep[cur]+1;
            dfs_bz(v);
        }
    }
}

void init() {
    for(int j=1;(1<for(int i=1;i<=n;i++) 
            if(f[i][j-1]!=-1)
                f[i][j]=f[f[i][j-1]][j-1];
}

int lca_bz(int x,int y) {
    if(deep[x]int d=deep[x]-deep[y];
    for(int i=0;d;i++,d>>=1) 
        if(d&1) x=f[x][i];

//  for(int i=0;(1<
//      if((1<

//  cout<
//  cout<
    if(x!=y) {
        for(int i=17;i>=0;i--) { //=0 ！！！
            if(f[x][i]!=f[y][i])
                x=f[x][i],y=f[y][i];
        }
        return f[x][0];
    }
    else return x;
}

int main(){
    scanf("%d %d %d",&n,&qu,&root);
    for(int i=1;iint a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    f[root][0]=-1;
    dfs_bz(root);
    init();
    for(int i=1;i<=qu;i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d
",lca_bz(x,y));
    }
    return 0;
}

3.tarjan

クエリーの問題をdfsに記録し、ノード(u)が戻るたびに問題を構成するすべてのノード(v)をクエリーし、以前に遍歴したノード(vis[v]=true)がある場合、この2つのノードのlcaはfind(v)であり、すべてのvを調べた後、親ノードの集合とマージし、その後に戻る.
code;

//By Menteur_Hxy 912ms
#include
#include
#include
using namespace std;

const int MAX=500010;

int n,qu,root,cnt;
int head[MAX],f[MAX],head_[MAX],vis[MAX],ans[MAX];

struct edges{
    int to,next;
}edge[MAX*2],edge_[MAX*2];

void add(int x,int y) {
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}

void add_(int x,int y) {
    edge_[++cnt].to=y;
    edge_[cnt].next=head_[x];
    head_[x]=cnt;
}

int find(int x) {
    return f[x]==x?x:f[x]=find(f[x]);
}

void tarjan(int u,int pre) {
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=pre) {
            tarjan(v,u);
            int a=find(v),b=find(u);
            f[a]=b;
        }   
    }
    for(int i=head_[u];i;i=edge_[i].next) {
        int v=edge_[i].to;
        if(vis[v]) 
            ans[(i+1)/2]=find(v);
    }
}

int main() {
    scanf("%d %d %d",&n,&qu,&root);
    for(int i=1;iint a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    f[n]=n;
    cnt=0;
    for(int i=1;i<=qu;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        add_(a,b);
        add_(b,a);
    }
    tarjan(root,-1);
    for(int i=1;i<=qu;i++) 
        printf("%d
",ans[i]);
    return 0;
}

posted @
2018-02-25 09:05 Menteur_Hxy読書(
...) コメント(
...) コレクションの編集