日度归档：25 9 月, 2019

洛谷 P3379 【模板】最近公共祖先（LCA）重写

发表评论

朴素算法：洛谷70分,O2 80分

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
#include<iostream>
#include<vector>
using namespace std;
int n, m, s;
vector<int> edges[500005];
int father[500005],depth[500005];
void dfs(int node, int fath) {
    father[node] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    while (a != b) {
        if (depth[a] >= depth[b])a = father[a];
        else b = father[b];
    }
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

倍增：洛谷80分，O2 100分

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
#include<iostream>
#include<vector>
#include<algorithm>
#define MAXLOG 20
using namespace std;
int n, m, s;
vector<int> edges[500005];
int depth[500005];
int ancestor[500005][MAXLOG+2];
void dfs(int node, int fath) {
    ancestor[node][0] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    if (depth[b] > depth[a])swap(a, b);
    for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i];
    if (a == b)return a;
    for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){
        a = ancestor[a][i];
        b = ancestor[b][i];
    }
    return ancestor[a][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

Tarjan:洛谷70分，O2 100分

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, s;
vector<int> edges[500005],askPair[500005];
bool visited[500005];
int father[500005];
inline int _find(int node) {
    if (father[node]==-1)return node;
    return father[node] = _find(father[node]);
}
inline void _union(int x, int y) {
    if(_find(x)!=_find(y))father[_find(x)] = y;
}
struct ask {
    int u, v;
    int ans;
}asks[500005];
inline int checkV(int id,int node) {
    if (asks[id].u != node)return asks[id].u;
    return asks[id].v;
}
void dfs(int node,int fath) {
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i],node);
        _union(edges[node][i], node);
    }
    visited[node] = true;
    for (int i = 0; i < askPair[node].size(); i++) {
        int v = checkV(askPair[node][i], node);
        if (visited[v])asks[askPair[node][i]].ans = _find(v);
    }
}
int main() {
    memset(father, -1, sizeof(father));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        cin >> asks[i].u >> asks[i].v;
        askPair[asks[i].u].push_back(i);
        askPair[asks[i].v].push_back(i);
    }
    dfs(s,s);
    for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n";
}