POJ 1330 Nearest Common Ancestors

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

典型的LCA模板题，三种算法都可以过。

题目链接 POJ 1330

题目大意

给你一棵树，让你求树上某两个节点的LCA。直接套模板即可。

LCA模板详解链接

LCA-RMQ-ST算法

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 100005
struct node
{
        int x;
};
vector<node> V[maxn]; //储存树的结构，也可以使用邻接表
int E[maxn * 2], D[maxn * 2], first[maxn]; //标号数列   深度数列   某个标号第一次出现的位置
int vis[maxn], dis[maxn], n, m, top = 1, root[maxn], st; //dis[] 若边有权值可求距离   root[] 求整棵树的根
int dp[30][maxn * 2];  //储存某区间最小值的下标
void init()
{
        top = 1;
        memset(root, 0, sizeof(root));
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
                V[i].clear();
        }
        int a, b;
        node tmp;
        for (int i = 0; i < n - 1; i++)
        {
                scanf("%d%d", &a, &b);
                tmp.x = b;
                V[a].push_back(tmp);
                tmp.x = a;
                V[b].push_back(tmp);
                root[b] = 1;
        }
        for (int i = 1; i <= n; i++)
                if (root[i] == 0)
                {
                        st = i;
                        break;
                }
}
void dfs(int u, int dep)
{
        vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++;
        for (int i = 0; i < V[u].size(); i++)
                if (!vis[V[u][i].x]) //储存时双向，因此判断是否为父节点
                {
                        int v = V[u][i].x;
                        dfs(v, dep + 1);
                        E[top] = u, D[top++] = dep; //dfs回溯过程必须储存，否则原理就错误了
                }
}
void ST(int num)
{
        for (int i = 1; i <= num; i++)//初始状态
        {
                dp[0][i] = i;
        }
        for (int i = 1; i <= log2(num); i++) //控制区间长度
                for (int j = 1; j <= num; j++) //控制区间左端点
                        if (j + (1 << i) - 1 <= num)
                        {
                                int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)];
                                if (D[a] < D[b]) //储存D数组下标，以便找到对应的E数组
                                {
                                        dp[i][j] = a; 
                                }
                                else
                                {
                                        dp[i][j] = b;
                                }
                        }
}
int RMQ(int x, int y)
{
        int k = (int) log2(y - x + 1.0);
        int a = dp[k][x], b = dp[k][y - (1 << k) + 1];
        if (D[a] < D[b]) //前后两段比较
        {
                return a;
        }
        return b;
}
int main ()
{
        int T;
        scanf("%d", &T);
        while (T--)
        {
                init();
                dfs(st, 0);
                ST(top);
                int x, y;
                scanf("%d%d", &x, &y);
                int a = first[x], b = first[y];
                if (a > b)
                {
                        swap(a, b);
                }
                int pos = RMQ(a, b);
                printf("%d\n", E[pos]);
        }
        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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 10005
int pre[maxn], point[maxn], point2[maxn];
// 储存树  树的邻接表数组  要查询的边的邻接表数组
bool vis[maxn];
//是否完全遍历
struct Edge
{
        int v; //连接点
        int next; //下一条从此边的出发点发出的边的序号
} edge[maxn * 2]; //邻接表   跟邻接矩阵一样，就是一种表示连接关系的结构
struct Query
{
        int v;
        int w; //找到后LCA后用来储存LCA的
        int next;
} query[maxn]; //要查询的边的邻接表
int top, top2; //两邻接表的下标变量
int init()
{
        memset(vis, 0, sizeof(vis));
        memset(point, -1, sizeof(point)); //邻接表数组初始化，一般都初始化为-1
        memset(point2, -1, sizeof(point2));
        top = 0;
        top2 = 0;
}
int add_edge(int u, int v) //加边函数，单向的
{
        edge[top].v = v;
        edge[top].next = point[u]; ///上一条边的编号
        point[u] = top++; //更新 储存该点刚才所连接的边的编号
}
int add_query(int u, int v) //要查询的边的加边函数，双向的
{
        query[top2].v = v;
        query[top2].w = -1;
        query[top2].next = point2[u];
        point2[u] = top2++;
        query[top2].v = u;
        query[top2].w = -1;
        query[top2].next = point2[v];
        point2[v] = top2++;
}
int findset(int x) ///并查集
{
        if (x != pre[x])
        {
                pre[x] = findset(pre[x]); //路径压缩
        }
        return pre[x];
}
int lca(int u, int f) ///当前节点，父节点
{
        pre[u] = u; ///设立当前节点的集合 表示该点是树的根
        for (int i = point[u]; i != -1; i = edge[i].next)
        {
                if (edge[i].v == f)
                {
                        continue;
                }
                lca(edge[i].v, u); ///搜索子树
                pre[edge[i].v] = u; ///合并子树
        }
        vis[u] = 1; ///以u点为集合的点搜索完毕
        for (int i = point2[u]; i != -1; i = query[i].next)
        {
                if (vis[query[i].v] == 1)
                {
                        query[i].w = findset(query[i].v); //储存LCA
                }
        }
        return 0;
}
int main()
{
        int root[maxn];
        int T;
        scanf("%d", &T);
        for (int ii = 0; ii < T; ii++)
        {
                init();
                int tot, r = -1, a, b;
                scanf("%d", &tot);
                for (int i = 1; i <= tot; i++)
                {
                        root[i] = i;
                }
                for (int i = 0; i < tot - 1; i++)
                {
                        scanf("%d%d", &a, &b);
                        add_edge(a, b);
                        add_edge(b, a);
                        root[b] = a;
                }
                for (int i = 1; i <= tot; i++)
                        if (root[i] == i)
                        {
                                r = i;        ///树的根
                        }
                scanf("%d%d", &a, &b);
                add_query(a, b);
                lca(r, r);
                for (int i = 0; i < top2; i++)
                {
                        if (query[i].w != -1)
                        {
                                printf("%d\n", query[i].w);
                        }
                }
        }
        return 0;
}

倍增算法（在线）

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#pragma comment(linker, "/STACK:10240000000,10240000000")//扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 100005;
int n , m , pre[N] , rt[N], mcnt;//pre 邻接表数组  rt 求根节点 mcnt 邻接表下标变量
bool vis[N];
struct edge
{
        int x , next;
} e[N << 1]; //邻接表
int dep[N] , f[17][N] , Lev , s[N];
//dep[]储存深度   1<<16 < N  f[j][i] 表示i的第2^j个祖先 s[]孩子个数
void init()
{
        memset(pre , -1 , sizeof(pre));
        memset(rt, 0, sizeof(rt));
        mcnt = 0;
}
void addedge(int x, int y)//邻接表加边函数
{
        e[mcnt].x = y,
        e[mcnt].next = pre[x],
        pre[x] = mcnt ++;
}
void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
        dep[x] = dep[fa] + 1;
        f[0][x] = fa , s[x] = 1;
        for (int i = pre[x] ; i!=-1 ; i = e[i].next)
        {
                int y = e[i].x;
                if (y != fa)
                {
                        dfs(y , x);
                        s[x] += s[y];///节点x的孩子个数
                }
        }
}
//	dfs处理后，要进一步处理得到节点的所有祖先
//	for (j = 1 ; 1 << j < n ; ++ j)
//		for (i = 1 ; i <= n ; ++ i)
//		{
//			f[j][i] = f[j - 1][f[j - 1][i]];
//		}
//	Lev = j - 1;
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
        queue<int> q;
        q.push(rt);
        f[0][rt] = 0, dep[rt] = 1, vis[rt] = 1;
        while (!q.empty())
        {
                int fa = q.front();
                q.pop();
                for (int i = pre[fa] ; ~i ; i = e[i].next)
                {
                        int x = e[i].x;
                        if (!vis[x])
                        {
                                dep[x] = dep[fa] + 1;
                                f[0][x] = fa , vis[x] = 1;
                                q.push(x);
                        }
                }
        }
}
int LCA(int x , int y)
{
        if (dep[x] > dep[y])
        {
                swap(x , y);
        }
        for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
                if (dep[y] - dep[x] >> i & 1)//dep[y]-dep[x]刚好比2的i次方大时
                {
                        y = f[i][y];
                }
        if (x == y)
        {
                return y;
        }
        for (int i = Lev ; i >= 0 ; -- i)//同一高度后开始找祖先
                if (f[i][x] != f[i][y])//不停的上次2的i次方，直到i==0
                {
                        x = f[i][x] , y = f[i][y];
                }
        return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
        for (int i = 0 ; i <= Lev ; ++ i)
                if (k >> i & 1)
                {
                        x = f[i][x];
                }
        return x;
}
void work()
{
        int i , j , x , y , z, anc;
        init();
        scanf("%d", &n);
        for (i = 1 ; i < n ; ++ i)
        {
                scanf("%d%d", &x, &y);
                addedge(x, y);
                addedge(y,x);
                rt[y]  = x;
        }
        for (int i = 1; i <= n; i++)
        {
                if (rt[i] == 0)
                {
                        anc = i;
                        break;
                }
        }
        dfs(anc , 0);
        for (j = 1 ; 1 << j < n ; ++ j)
                for (i = 1 ; i <= n ; ++ i)
                {
                        f[j][i] = f[j - 1][f[j - 1][i]];
                }
        Lev = j - 1;
        scanf("%d%d", &x, &y);
        printf("%d\n", LCA(x , y));
}
int main()
{
        int t;
        scanf("%d", &t);
        while (t--)
        {
                work();
        }
        return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！