常用图论算法

发表于 更新于 分类于 阅读次数： 本文字数： 364 阅读时长 ≈ 1 分钟
A good medicine tastes bitter.

图论(Graph Theory)

LCA (最近公共祖先)

查找最近公共祖先的方法：

  1. 向上标记法

  2. 倍增法

    • 表示从 开始，向上走 步所能到达的节点，
    • 表示深度

    步骤：

    1. 先将两个点跳到同一层。
    2. 让两个点同时向上跳，直到跳到他们的最近公共祖先的下一层。

    预处理

    查询

  3. 离线求

练习

祖孙询问

算法：倍增法求 

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
#include <bits/stdc++.h> 

using i64 = int64_t;

constexpr int N = 4E4 + 10;
int f[N][20], dep[N];

int lca(int x, int y) {
    if (dep[x] < dep[y]) {
        std::swap(x, y);
    }

    for (int i = 19; i >= 0; i--) {
        if (dep[f[x][i]] >= dep[y]) {
            x = f[x][i];
        }		
    }

    if (x == y) return x;

    for (int i = 19; i >= 0 && y != x; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int rt = -1;
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < n; i++) {
        int u, v;
        std::cin >> u >> v;

        if (v == -1) {
            rt = u;
            continue ;
        }

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
     
    auto dfs = [&](auto self, int u, int fa) -> void {
        f[u][0] = fa;
        dep[u] = dep[f[u][0]] + 1;

        for (int i = 1; i < 20; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }

        for (auto x : adj[u]) {
            if (x == fa) continue ;
            self(self, x, u);
        }
    };
    dfs(dfs, rt, 0);

     int q;
     std::cin >> q;

     while (q--) {
         int x, y;
         std::cin >> x >> y;

         int ans = 0;
         if (lca(x, y) == x) {
             ans = 1;
         } else if (lca(x, y) == y) {
             ans = 2;
         }
         std::cout << ans << "\n";
     }

    return 0;
}