LCA

发表于 | 分类于 | 阅读次数:

##倍增法

在线算法

时间复杂度：

  • 预处理：$O(N)$
  • 查询：$O(log_2N)$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int m,n,q,anc[100][32],deep[100];

    int head[100],cnt; 
    struct mine
    {
    	int to,next;
    }edge[100];
    void swap(int &a,int &b){int t=a;a=b;b=t;}
    void add(int x,int y)
    {
    	cnt++;
    	edge[cnt].to=y;
    	edge[cnt].next=head[x];
    	head[x]=cnt;
    }
    void dfs(int now,int from)
    {
    	for(int tmp=head[now];tmp!=0;tmp=edge[tmp].next)
    	{
    		if(edge[tmp].to==from) continue;//遍历无向图时防止死循环
    		deep[edge[tmp].to]=deep[now]+1;
    		dfs(edge[tmp].to,now);
    		anc[edge[tmp].to][0]=now;
    	}
    }
    void ready()
    {
    	for(int i=1;(1<<i)<=n;i++)
    		for(int j=1;j<=n;j++)
    			anc[j][i]=anc[anc[j][i-1]][i-1];
    }
    int getlca(int x,int y)
    {
    	if(deep[x]<deep[y]) swap(x,y);
    	int maxlogn=floor(log(n)/log(2));
    	for(int i=maxlogn;i>=0;i--)
    		if(deep[x]-(1<<i)>=deep[y])
    		       	x=anc[x][i];
    	if(x==y) return x;
    	for(int i=maxlogn;i>=0;i--)
    		if(anc[x][i]!=anc[y][i])
    		{
    			x=anc[x][i];y=anc[y][i];
    		}
    	return anc[x][0];
    }
    int main()
    {
    	freopen("lca.in", "r", stdin);
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++)
    	{
            	int u, v;
            	cin >> u >> v;
         		add(u, v);
            	add(v, u);
       	}	
       	dfs(1,1);
       	ready();
       	for (int i = 1; i <= n; i++) 
           	for (int j = i; j <= n; j++)
        	   	cout << i << " " << j << " " << getlca(i, j) << endl;
    	return 0;
    }

##Tarjan法
离线算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
using namespace std;

int n,m,root,edge_num,ask_num;
int fa[500010],head[1200000],h1[1200000],ans[500010];
bool b[500010];

struct E{
    int next,to;
}edge[1200000];
struct A{
    int next,to,num;
}ask[1200000];

void addedge(int x,int y){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    head[x]=edge_num;
}
void addask(int x,int y,int z){
    ask[++ask_num].next=h1[x];
    ask[ask_num].to=y;
    ask[ask_num].num=z;
    h1[x]=ask_num;
}

int Find(int x){
    if(fa[x]!=x) fa[x]=Find(fa[x]);
    return fa[x];
}

/*void Union(int a,int b){
    a=Find(a);b=Find(b);
    fa[a]=b;
}*/

void LCA(int x){
    b[x]=1;
    fa[x]=x;
    int j,u;
    for(j=head[x];j;j=edge[j].next){
        u=edge[j].to;
        if(!b[u]){
            LCA(u);
            fa[u]=x;
        }
    }
    int k;
    for(j=h1[x];j;j=ask[j].next){
        u=ask[j].to;
        k=ask[j].num;
        if(b[u]){
            ans[k]=Find(u);
        }
    }
}

void out(){
    for(int o=1;o<=m;o++){
        printf("%d\n",ans[o]);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&root);
    int i,ask1,ask2,a1,b1;
    for(i=1;i<=n-1;i++){
        scanf("%d%d",&a1,&b1);
        addedge(a1,b1);addedge(b1,a1);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&ask1,&ask2);
        addask(ask1,ask2,i);
        addask(ask2,ask1,i);
    }
    LCA(root);
    out();
    return 0;
}

##RMQ法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int MAXN=500000,MAXM=100;
int a[MAXN+1],pa=0;int na[MAXN+1];
int f[MAXN+1][MAXM+1];

int head[MAXN+1],ecnt;
struct node{int to,next;} edge[MAXN+1];
void add(int x,int y)
{
	ecnt++;
	edge[ecnt].to=y;
	edge[ecnt].next=head[x];
	head[x]=ecnt;
}

void Init()
{  
    for (int i = 1; i <= pa; i++)
        f[i][0] = a[i];
    for (int k = 1; (1 << k) <= pa; k++)
        for (int i = 1; i + (1 << k) - 1 <= pa; i++)
            f[i][k] = min(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}

int RMQ(int l, int r)
{  
    int k = 0;
    while( (1 << (k + 1)) <= r - l + 1 ) k++;
    return min( f[l][k], f[r - (1 << k) + 1][k] );
}

void dfs(int x,int d)
{
	for(int tmp=head[x];tmp;tmp=edge[tmp].next)
	{
		a[++pa]=d;na[pa]=x;
		dfs(edge[tmp].to,d+1);
	}
	 a[++pa]=d;na[pa]=x;
}
int main()
{
	int u,v,N,M,S,x,y,xp,yp;
	cin>>N>>M>>S;
	for(int i=1;i<=N-1;i++)
		cin>>u>>v,add(v,u);
	dfs(S,1);
	Init();
	for(int i=1;i<=M;i++)
	{	
		cin>>x>>y;
		for(int i=1;i<=pa;i++) if(na[i]==x){xp=i;break;}
		for(int i=1;i<=pa;i++) if(na[i]==y){yp=i;break;}
		if(xp>yp) swap(xp,yp);
		cout<<na[RMQ(xp,yp)]<<endl;
	}
	return 0;
}