Hexo
0%

最近公共祖先

Posted on In , ,
Symbols count in article: 2.6k Reading time ≈ 2 mins.

最近公共祖先LCA

倍增算法

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
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define endl "\n"
int head[N], to[N<<1], nex[N<<1], cnt=1;
int fa[N][21], dep[N];
void add(int x, int y){
	to[cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt++;
}
void dfs(int rt, int f){
	dep[rt] = dep[f] + 1;
	fa[rt][0] = f;
	for(int i = 1; (1 << i) <= dep[rt]; i++){ //进制由小到大递推 
		fa[rt][i] = fa[fa[rt][i - 1]][i - 1];
	}
	for(int i = head[rt]; i; i = nex[i]){
		if(to[i] == f){
			continue;
		}
		dfs(to[i], rt);
	}
}
int LCA(int x, int y){
	if(dep[x] < dep[y]){
		swap(x, y);
	}
	for(int i = 20; i >= 0; i--){ //进制由大到小开始组合 
		if(dep[fa[x][i]] >= dep[y]){
			x = fa[x][i];
		}
	} 
	if(x == y){ //注意特判 
		return x;
	}
	for(int i = 20; i >= 0; i--){ //进制从小到大开始组合 
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0]; //这一步尤其考虑，为什么x,y不是LCA，二期父节点一定是LCA 
}
int main(){
	ios::sync_with_stdio(false);
	int n, m, s;
	while(cin >> n >> m >> s){
		memset(head, 0, sizeof(head));
		cnt = 1;
		int x, y;
		for(int i = 0; i < n - 1; i++){
			cin >> x >> y;
			add(x, y);
			add(y, x);
		}
		dfs(s, 0);
		for(int i = 0; i < m; i++){
			cin >> x >> y;
			cout << LCA(x, y) << 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
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define N 500005
int head[N], to[N<<1], nex[N<<1], cnt ;
int visit[N], fa[N];
int qhead[N<<1], qnex[N<<1], qcnt = 1, qid[N<<1], ans[N], qto[N<<1];
void add_edge(int x, int y){
	to[cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt++;
}
void add_query(int x, int y, int w){
	qto[qcnt] = y;
	qnex[qcnt] = qhead[x];
	qid[qcnt] = w;
	qhead[x] = qcnt++;
}
int findx(int x){
	if(fa[x] == x){
		return x;
	}
	return fa[x] = findx(fa[x]);
}
void tarjan(int rt, int f){
	for(int i = head[rt]; i; i = nex[i]){
		if(to[i] == f)continue;
		tarjan(to[i], rt);
		fa[to[i]] = rt;
	}
	visit[rt] = 1;
	for(int i = qhead[rt]; i; i = qnex[i]){
		if(visit[qto[i]] == 0)continue; 
		ans[qid[i]] = findx(qto[i]);
	}
	
}
int main(){
	ios::sync_with_stdio(false);
	int n, m, s;
	while(cin >> n >> m >> s){
		int x, y;
		memset(head, 0, sizeof(head));
		cnt = 1, qcnt = 1;
		memset(qhead, 0, sizeof(qhead));
		for(int i = 1; i < n; i++){
			cin >> x >> y;
			add_edge(x, y);
			add_edge(y, x);
			fa[i] = i;
		}
		fa[n] = n;
		for(int i = 1; i <= m; i++){
			cin >> x >> y;
			add_query(x, y, i);
			add_query(y, x, i);
		}
		tarjan(s, 0);
		for(int i = 1; i <= m; i++){
			cout << ans[i] << endl;
		}
	}
	return 0;
}