算法模版-图论

发表于 更新于 分类于 阅读次数： 本文字数： 30k
图论算法模版，慢慢更新。

图论

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::vector<i64> dis(n + 1, 1e18);
auto dijkstra = [&](int s) {
    using PII = std::pair<i64, int>;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;
    pq.push({0, s});
    dis[s] = 0;
    std::vector<bool> vis(n + 1);
    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        if (vis[x]) {
            continue;
        }
      	vis[x] = true;
        for (auto [y, w] : adj[x]) {
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                pq.push({dis[y], y});
            }
        }
    }
};

Floyd

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
const int N = 210;
int n, m, d[N][N];

void floyd() {
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while (m --) {
        int x, y, w; cin >> x >> y >> w;
        d[x][y] = min(d[x][y], w);
    }
    floyd();
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (d[i][j] > INF / 2) cout << "N" << endl;
            else cout << d[i][j] << endl;
        }
    }
}

SPFA

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
std::vector<i64> dis(n + 1, 1e18);
    auto spfa = [&](int n, int s) {
        std::vector<bool> vis(n + 1);
        std::vector<int> cnt(n + 1);
        dis[s] = 0;
        vis[s] = true;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            vis[x] = false;
            for (auto [y, w] : adj[x]) {
                if (dis[y] > dis[x] + w) {
                    dis[y] = dis[x] + w;
                    cnt[y] = cnt[x] + 1;
                    if (cnt[y] >= n) {
                        return false;
                    }
                    if (!vis[y]) {
                        q.push(y);
                        vis[y] = true;
                    }
                }
            }
        }
        return true;
    };

拓扑排序

注意拓扑找环时不能用 vis 数组判断，而应该使用 cnt 记录使用的节点数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cnt = 0;
   while (!que.empty()) {
       auto [x, v] = que.front();
       que.pop();
       cnt++;
       for (auto y : adj[x]) {
           deg[y]--;
           if (deg[y] == 0) {
               que.push({y, v + 1});
           }
       }
   }
   if (cnt != n + 1) {
       std::cout << "NO\n";
       return;
   }

强连通分量 SCC 缩点

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
struct SCC {
    int n, now, cnt;
    std::vector<std::vector<int>> ver;
    std::vector<int> dfn, low, bel, stk;
    SCC(int n) : n(n), ver(n + 1), low(n + 1) {
        dfn.resize(n + 1, -1);
        bel.resize(n + 1, -1);
        now = cnt = 0;
    }
    void add(int x, int y) { ver[x].push_back(y); }
    void tarjan(int x) {
        dfn[x] = low[x] = now++;
        stk.push_back(x);
        for (auto y : ver[x]) {
            if (dfn[y] == -1) {
                tarjan(y);
                low[x] = std::min(low[x], low[y]);
            } else if (bel[y] == -1) {
                low[x] = std::min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x]) {
            int y;
            cnt++;
            do {
                y = stk.back();
                stk.pop_back();
                bel[y] = cnt;
            } while (y != x);
        }
    }
    auto work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == -1) {
                tarjan(i);
            }
        }
        std::vector<int> siz(cnt + 1);
        std::vector<std::vector<int>> adj(cnt + 1);
        for (int i = 1; i <= n; i++) {
            siz[bel[i]]++;
            for (auto j : ver[i]) {
                int x = bel[i], y = bel[j];
                if (x != y) {
                    adj[x].push_back(y);
                }
            }
        }
        return std::tuple{cnt, adj, bel, siz};
    }
};

边双连通分量 EDCC 缩点

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
struct EDCC {
    int n, now, cnt;
    std::vector<std::vector<int>> ver;
    std::vector<int> dfn, low, bel, S;
    std::set<std::array<int, 2>> bridge;

    EDCC(int n) : n(n), ver(n + 1), low(n + 1) {
        dfn.resize(n + 1, -1);
        bel.resize(n + 1, -1);
        now = cnt = 0;
    }
    void add(int x, int y) {
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void tarjan(int x, int fa) {
        dfn[x] = low[x] = now++;
        S.push_back(x);
        for (auto y : ver[x]) {
            if (y == fa) {
                continue;
            }
            if (dfn[y] == -1) {
                tarjan(y, x);
                low[x] = std::min(low[x], low[y]);
                if (low[y] > dfn[x]) {
                    bridge.insert({x, y});
                }
            } else {
                low[x] = std::min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x]) {
            int pre;
            cnt++;
            do {
                pre = S.back();
                bel[pre] = cnt;
                S.pop_back();
            } while (pre != x);
        }
    }
    auto work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == -1) {
                tarjan(i, 0);
            }
        }

        std::vector<int> siz(cnt + 1);
        std::vector<std::vector<int>> adj(cnt + 1);
        for (int i = 1; i <= n; i++) {
            siz[bel[i]]++;
            for (auto j : ver[i]) {
                int x = bel[i], y = bel[j];
                if (x != y) {
                    adj[x].push_back(y);
                }
            }
        }
        return std::tuple{cnt, adj, bel, siz};
    }
};

点双连通分量 VDCC 缩点

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
struct VDCC {
    int n, now;
    std::vector<std::vector<int>> ver, bcc;
    std::vector<int> dfn, low, stk;
    std::vector<bool> point;
    VDCC(int n) : n(n) {
        ver.resize(n + 1);
        dfn.resize(n + 1, -1);
        low.resize(n + 1);
        point.resize(n + 1);
        now = 0;
    }
    void add(int x, int y) {
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void tarjan(int x, int fa) {
        low[x] = dfn[x] = now++;
        stk.push_back(x);
        int child = 0;
        for (auto y : ver[x]) {
            if (dfn[y] == -1) {
                tarjan(y, x);
                low[x] = std::min(low[x], low[y]);
                if (low[y] >= dfn[x] && fa != 0) {
                    point[x] = true;
                }
                if (low[y] >= dfn[x]) {
                    bcc.emplace_back();
                    int z;
                    do {
                        z = stk.back();
                        stk.pop_back();
                        bcc.back().push_back(z);
                    } while (z != y);
                    bcc.back().push_back(x);
                }
                child++;
            } else {
                low[x] = std::min(low[x], dfn[y]);
            }
        }
        if (fa == 0 && child >= 2) {
            point[x] = true;
        }
        if (fa == 0 && child == 0) {
            bcc.push_back({x});
            stk.pop_back();
        }
    }
    auto work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == -1) {
                tarjan(i, 0);
            }
        }
        int B = bcc.size();
        vector<int> apId(n + 1, 0);
        int A = 0;
        for (int u = 1; u <= n; u++) {
            if (point[u]) {
                apId[u] = ++A;
            }
        }
        int tot = B + A;
        vector<vector<int>> adj(tot + 1);
        vector<int> bel(n + 1, 0), siz(tot + 1, 0);
        for (int i = 0; i < B; i++) {
            int bid = i + 1;
            siz[bid] = (int)bcc[i].size();
            for (int u : bcc[i]) {
                if (point[u]) {
                    int aid = B + apId[u];
                    adj[bid].push_back(aid);
                    adj[aid].push_back(bid);
                } else {
                    bel[u] = bid;
                }
            }
        }
        for (int u = 1; u <= n; u++) {
            if (point[u]) {
                int aid = B + apId[u];
                bel[u] = aid;
                siz[aid] = 1;
            }
        }
        for (int i = 1; i <= tot; i++) {
            auto &v = adj[i];
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
        }
        return tuple{tot, adj, bel, siz};
    }
};

圆方树

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
int ext = n, dfc = 0;
std::vector<int> dfn(2 * n), low(n + 1), stk;
std::vector<std::vector<int>> adj(2 * n);
std::function<void(int)> tarjan = [&](int x) {
    dfn[x] = low[x] = ++dfc;
    stk.push_back(x);
    for (auto y : ver[x]) {
        if (!dfn[y]) {
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
            if (low[y] == dfn[x]) {
                ext++;
                while (true) {
                    int tp = stk.back();
                    stk.pop_back();
                    adj[ext].push_back(tp);
                    adj[tp].push_back(ext);
                    if (tp == y) {
                        break;
                    }
                }
                adj[ext].push_back(x);
                adj[x].push_back(ext);
            }
        } else {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
};
tarjan(1);
stk.pop_back();

2-SAT

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
struct TwoSat {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<bool> ans;
    TwoSat(int n) : n(n) {
        adj.resize(2 * n + 1);
        ans.resize(n + 1);
    }
    void add(int x, bool f, int y, bool g) {
        adj[x + !f * n].push_back(y + g * n);
        adj[y + !g * n].push_back(x + f * n);
    }
    bool work() {
        std::vector<int> id(2 * n + 1, -1), dfn(2 * n + 1, -1), low(2 * n + 1);
        std::vector<int> stk;
        int now = 0, cnt = 0;
        auto tarjan = [&](auto tarjan, int x) -> void {
            stk.push_back(x);
            dfn[x] = low[x] = now++;
            for (auto y : adj[x]) {
                if (dfn[y] == -1) {
                    tarjan(tarjan, y);
                    low[x] = std::min(low[x], low[y]);
                } else if (id[y] == -1) {
                    low[x] = std::min(low[x], dfn[y]);
                }
            }
            if (low[x] == dfn[x]) {
                int y;
                cnt++;
                do {
                    y = stk.back();
                    stk.pop_back();
                    id[y] = cnt;
                } while (y != x);
            }
        };
        for (int i = 1; i <= 2 * n; i++) {
            if (dfn[i] == -1) {
                tarjan(tarjan, i);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (id[i] == id[i + n]) {
                return false;
            }
            ans[i] = id[i] < id[i + n];
        }
        return true;
    }
};

二分图染色，判断二分图（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::queue<int> q;
std::vector<int> f(n + 1, -1);
bool ok = true;
for (int i = 1; i <= n; i++) {
    if (f[i] == -1) {
        q.push(i);
        f[i] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (auto y : adj[x]) {
                if (f[y] == -1) {
                    f[y] = f[x] ^ 1;
                    q.push(y);
                } else if (f[x] == f[y]) {
                    ok = false;
                    break;
                }
            }
        }
    }
}

二分图最大匹配（增广路）

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
struct AugmentPath {
    std::vector<std::vector<int>> adj;
    std::vector<int> pa;
    std::vector<int> pb;
    std::vector<int> vis;
    int n, m;
    int dfn, res;
    AugmentPath(int n_, int m_) : n(n_), m(m_) {
        pa.resize(n + 1, -1);
        pb.resize(m + 1, -1);
        vis.resize(n + 1);
        adj.resize(n + 1);
        res = dfn = 0;
    }
    void add(int x, int y) { adj[x].push_back(y); }
    bool dfs(int x) {
        vis[x] = dfn;
        for (auto y : adj[x]) {
            if (pb[y] == -1) {
                pa[x] = y;
                pb[y] = x;
                return true;
            }
        }
        for (auto y : adj[x]) {
            if (vis[pb[y]] != dfn && dfs(pb[y])) {
                pa[x] = y;
                pb[y] = x;
                return true;
            }
        }
        return false;
    }
    int work() {
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

最小生成树（Kruskal）

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
struct DSU {
    int n;
    std::vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

struct Kruskal {
    int n;
    std::vector<std::array<int, 3>> e;
    Kruskal(int n) : n(n) {}
    void add(int w, int x, int y) { e.push_back({w, x, y}); }
    int work() {
        DSU dsu(n);
        int ans = 0, cnt = 0;
        sort(e.begin(), e.end());
        for (auto [w, x, y] : e) {
            if (dsu.same(x, y)) {
                continue;
            }
            dsu.merge(x, y);
            ans += w;
            cnt++;
        }
        if (cnt < n - 1) {
            return -1;
        }
        return ans;
    }
};

最小生成树（Prim）

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
struct Prim {
    int n;
    std::vector<int> dis;
    std::vector<bool> vis;
    std::vector<std::array<int, 3>> e;
    std::vector<std::vector<std::array<int, 2>>> adj;
    Prim(int n) { init(n); }
    void init(int n_) {
        n = n_;
        dis.resize(n + 1, 2e9);
        vis.resize(n + 1);
        adj.resize(n + 1);
    }
    void add(int w, int x, int y) {
        e.push_back({w, x, y});
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    int work() {
        int ans = 0, cnt = 0;
        dis[1] = 0;
        using PII = std::pair<int, int>;
        std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;
        pq.push({0, 1});
        while (!pq.empty()) {
            auto [w, x] = pq.top();
            pq.pop();
            if (vis[x]) {
                continue;
            }
            vis[x] = true;
            cnt++;
            ans += w;
            for (auto [y, w] : adj[x]) {
                if (w < dis[y]) {
                    dis[y] = w;
                    pq.push({w, y});
                }
            }
        }
        return ans;
    }
};

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
struct HLD {
    int n, idx;
    std::vector<std::vector<int>> e;
    std::vector<int> siz, dep;
    std::vector<int> top, son, p;
    HLD(int n) {
        this->n = n;
        e.resize(n + 1);
        siz.resize(n + 1);
        dep.resize(n + 1);
        top.resize(n + 1);
        son.resize(n + 1);
        p.resize(n + 1);
    }
    void add(int x, int y) {
        e[x].push_back(y);
        e[y].push_back(x);
    }
    void dfs1(int x) {
        siz[x] = 1;
        dep[x] = dep[p[x]] + 1;
        for (auto y : e[x]) {
            if (y == p[x]) {
                continue;
            }
            p[y] = x;
            dfs1(y);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    }
    void dfs2(int x, int up) {
        top[x] = up;
        if (son[x]) {
            dfs2(son[x], up);
        }
        for (auto y : e[x]) {
            if (y == p[x] || y == son[x]) {
                continue;
            }
            dfs2(y, y);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] > dep[top[y]]) {
                x = p[top[x]];
            } else {
                y = p[top[y]];
            }
        }
        return dep[x] < dep[y] ? x : y;
    }
    int calc(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
    void work(int root = 1) {
        dfs1(root);
        dfs2(root, root);
    }
};

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
struct Tree {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> p;
    std::vector<int> dep;

    Tree(int n_ = 0) { init(n_); }

    void init(int n_) {
        n = n_;
        adj.assign(n + 1, {});
        p.assign(n + 1, std::vector<int>(30, 0));
        dep.assign(n + 1, 0);
    }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int x, int fa) {
        p[x][0] = fa;
        dep[x] = dep[fa] + 1;
        for (int y : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs(y, x);
        }
    }

    void work(int root = 1) {
        dfs(root, 0);
        for (int j = 1; j < 30; j++) {
            for (int i = 1; i <= n; i++) {
                p[i][j] = p[p[i][j - 1]][j - 1];
            }
        }
    }

    int lca(int x, int y) {
        if (dep[x] < dep[y]) {
            std::swap(x, y);
        }
        int d = dep[x] - dep[y];
        for (int j = 0; j < 30; j++) {
            if (d & (1 << j)) {
                x = p[x][j];
            }
        }
        if (x == y) {
            return x;
        }
        for (int j = 29; j >= 0; j--) {
            if (p[x][j] != p[y][j]) {
                x = p[x][j];
                y = p[y][j];
            }
        }
        return p[x][0];
    }

    int dis(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
};

树链剖分（路径修改，子树修改）

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        tag.assign(4 * (n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);
                return;
            }
            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        if (x <= mid) {
            modify(2 * p, l, mid, x, v);
        } else {
            modify(2 * p + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (x <= l && r <= y) {
            return info[p];
        }
        push(p);
        int mid = (l + r) / 2;
        return rangeQuery(2 * p, l, mid, x, y) +
               rangeQuery(2 * p + 1, mid + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (x <= l && r <= y) {
            apply(p, v);
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 1, n, l, r, v);
    }
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Tag {
    int add = 0;
    Tag() {}
    Tag(int x) : add(x) {}
    void apply(const Tag &t) { add += t.add; }
};

struct Info {
    int mx = -2e9;
    int v = 0;
    int size = 1;
    Info() {}
    Info(int v) : v(v), mx(v) {}
    void apply(const Tag &t) {
        v += size * t.add;
        mx += t.add;
    }
};

Info operator+(const Info &a, const Info &b) {
    Info info;
    info.size = a.size + b.size;
    info.v = a.v + b.v;
    info.mx = std::max(a.mx, b.mx);
    return info;
}

struct HLD {
    int n, idx;
    std::vector<std::vector<int>> adj;
    std::vector<int> siz, dep, top, son, p, in, id, val;
    LazySegmentTree<Info, Tag> seg;
    HLD(int n_) {
        n = n_;
        idx = 0;
        adj.resize(n + 1);
        siz.resize(n + 1);
        dep.resize(n + 1);
        top.resize(n + 1);
        son.resize(n + 1);
        p.resize(n + 1);
        in.resize(n + 1);
        id.resize(n + 1);
        val.resize(n + 1);
    }
    void add(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void dfs1(int x) {
        siz[x] = 1;
        dep[x] = dep[p[x]] + 1;
        for (auto y : adj[x]) {
            if (y == p[x]) {
                continue;
            }
            p[y] = x;
            dfs1(y);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    }
    void dfs2(int x, int up) {
        id[x] = ++idx;
        val[idx] = in[x];
        top[x] = up;
        if (son[x]) {
            dfs2(son[x], up);
        }
        for (auto y : adj[x]) {
            if (y == p[x] || y == son[x]) {
                continue;
            }
            dfs2(y, y);
        }
    }
  	int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] > dep[top[y]]) {
                x = p[top[x]];
            } else {
                y = p[top[y]];
            }
        }
        return dep[x] < dep[y] ? x : y;
    }
    int calc(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
    void modify(int x, int v) { seg.modify(id[x], Info(v)); }
    void rangeApply(int l, int r, int v) {
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]]) {
                std::swap(l, r);
            }
            seg.rangeApply(id[top[l]], id[l], v);
          	l = p[top[l]];
        }
        if (dep[l] > dep[r]) {
            std::swap(l, r);
        }
        seg.rangeApply(id[l], id[r], v);
    }
    void rangeApply(int root, int v) {
        seg.rangeApply(id[root], id[root] + siz[root] - 1, v);
    }
    int ask(int l, int r) {
        int ans = 0;
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]]) {
                std::swap(l, r);
            }
            ans += seg.rangeQuery(id[top[l]], id[l]).v;
            l = p[top[l]];
        }
        if (dep[l] > dep[r]) {
            std::swap(l, r);
        }
        return ans + seg.rangeQuery(id[l], id[r]).v;
    }
    int ask(int root) {
        return seg.rangeQuery(id[root], id[root] + siz[root] - 1).v;
    }
    int ask_max(int l, int r) {
        int ans = -2e9;
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]]) {
                std::swap(l, r);
            }
            ans = std::max(ans, seg.rangeQuery(id[top[l]], id[l]).mx);
            l = p[top[l]];
        }
        if (dep[l] > dep[r]) {
            std::swap(l, r);
        }
        return std::max(ans, seg.rangeQuery(id[l], id[r]).mx);
    }
    int ask_max(int root) {
        return seg.rangeQuery(id[root], id[root] + siz[root] - 1).mx;
    }
    void work(auto in, int root = 1) {
        assert(in.size() == n + 1);
        this->in = in;
        dfs1(root);
        dfs2(root, root);
        seg.init(val);
    }
    void work(int root = 1) {
        dfs1(root);
        dfs2(root, root);
        seg.init(val);
    }
};

欧拉路径

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<int> stk;
std::vector<int> del(m);
auto Euler = [&](auto Euler, int x) -> void {
    for (int i = del[x]; i < adj[x].size(); i = del[x]) {
        del[x] = i + 1;
        int y = adj[x][i];
        Euler(Euler, y);
    }
    stk.push_back(x);
};
Euler(Euler, start);
reverse(stk.begin(), stk.end());

树哈希

1
2
3
4
5
6
7
8
9
10
const u64 mask = std::mt19937_64(
    std::chrono::steady_clock::now().time_since_epoch().count())();
u64 shift(u64 x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

树的直径（两次DFS）

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
std::vector<i64> dep(n + 1);
std::vector<int> prefa(n + 1);
int c = 0;
auto dfs = [&](auto dfs, int x, int fa) -> void {
    for (auto [y, w] : adj[x]) {
        if (y == fa) {
            continue;
        }
        dep[y] = dep[x] + w;
        prefa[y] = x;
        if (dep[y] > dep[c]) {
            c = y;
        }
        dfs(dfs, y, x);
    }
};
dfs(dfs, 1, 0);
dep[c] = 0;
fill(prefa.begin() + 1, prefa.end(), 0);
dfs(dfs, c, 0);
std::vector<bool> diameter(n + 1);
int d = 0;
std::vector<int> path(1);
for (int i = c; i != 0; i = prefa[i]) {
    diameter[i] = true;
    d++;
    path.push_back(i);
}

树的直径（树形 dp）

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
std::vector<int> d1(n + 1), d2(n + 1); // 最长和次长路径长度
	std::vector<int> p1(n + 1, -1), p2(n + 1, -1); // 对应子节点
	int d = 0, center = 1; // 直径长度和中心节点

	auto dfs = [&](auto dfs, int x, int fa) -> void {
		d1[x] = d2[x] = 0;
		p1[x] = p2[x] = -1;
		for (auto y : adj[x]) {
			if (y == fa) continue;
			dfs(dfs, y, x);
			int t = d1[y] + 1;
			if (t > d1[x]) {
				d2[x] = d1[x], p2[x] = p1[x];
				d1[x] = t, p1[x] = y;
			} else if (t > d2[x]) {
				d2[x] = t, p2[x] = y;
			}
		}
		if (d1[x] + d2[x] > d) {
			d = d1[x] + d2[x];
			center = x;
		}
	};
	dfs(dfs, 1, 0);

	// 恢复路径
	auto trace = [&](int u, const std::vector<int> &from) {
		std::vector<int> path;
		while (u != -1) {
			path.push_back(u);
			u = from[u];
		}
		return path;
	};

	std::vector<int> left = trace(p1[center], p1);
	std::vector<int> right = trace(p2[center], p1);
	std::reverse(left.begin(), left.end());

	std::vector<int> path = left;
	path.push_back(center);
	path.insert(path.end(), right.begin(), right.end());

	std::cout << d << "\n"; // 输出直径长度
	for (int x : path) {
		std::cout << x << " ";
	}

Kruskal 重构树

结论：原图中两个点间所有路径上的边最大权值的最小值 = 最小生成树上两点简单路径的边最大权值 = Kruskal 重构树上两点 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
65
struct DSU {
    int n;
    std::vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // if (sz[x] > sz[y]) {
        //     std::swap(x, y);
        // }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

struct KruskalTree {
    int n;
    std::vector<std::array<int, 3>> e;
    DSU dsu;
    KruskalTree(int n) : n(n), dsu(2 * n - 1) {}
    void add(int w, int x, int y) { e.push_back({w, x, y}); }
    auto work() {
        std::vector<std::vector<int>> adj(2 * n);
        std::vector<int> val(2 * n);
        int cnt = 0;
        sort(e.begin(), e.end());
        int now = n;
        for (auto [w, x, y] : e) {
            x = dsu.find(x), y = dsu.find(y);
            if (dsu.same(x, y)) {
                continue;
            }
            now++;
            cnt++;
            dsu.merge(x, now);
            dsu.merge(y, now);
            val[now] = w;
            adj[now].push_back(y);
            adj[now].push_back(x);
            adj[y].push_back(now);
            adj[x].push_back(now);
        }
        return std::tuple{now, adj, val};
    }
};

最大流（Dinic）

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
template <class T>
struct MaxFlow {
    struct _Edge {
        int to;
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };
    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    MaxFlow() {}
    MaxFlow(int n) { init(n); }
    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n + 1, {});
        cur.resize(n + 1);
    }
    bool bfs(int s, int t) {
        h.assign(n + 1, -1);
        std::queue<int> q;
        h[s] = 0;
        q.push(s);
        while (!q.empty()) {
            const int u = q.front();
            q.pop();
            for (auto i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < g[u].size(); i++) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n + 1, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }
    std::vector<bool> minCut() {
        std::vector<bool> c(n + 1);
        for (int i = 1; i <= n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

最小费用最大流

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
template <class T>
struct MinCostFlow {
    struct _Edge {
        int to;
        T cap;
        T cost;
        _Edge(int to_, T cap_, T cost_) : to(to_), cap(cap_), cost(cost_) {}
    };

    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<T> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n + 1, std::numeric_limits<T>::max());
        pre.assign(n + 1, -1);
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                            std::greater<std::pair<T, int>>>
            pq;
        dis[s] = 0;
        pq.emplace(0, s);
        while (!pq.empty()) {
            T d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if (dis[u] != d) {
                continue;
            }
            for (auto i : g[u]) {
                int v = e[i].to;
                T cap = e[i].cap;
                T cost = e[i].cost;
                if (cap > 0 && dis[v] > d + h[u] - h[v] + cost) {
                    dis[v] = d + h[u] - h[v] + cost;
                    pre[v] = i;
                    pq.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<T>::max();
    }
    MinCostFlow() {}
    MinCostFlow(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        e.clear();
        g.assign(n + 1, {});
    }
    void addEdge(int u, int v, T cap, T cost) {
        g[u].push_back(e.size());
        e.emplace_back(v, cap, cost);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -cost);
    }
    std::pair<T, T> flow(int s, int t) {
        T flow = 0;
        T cost = 0;
        h.assign(n + 1, 0);
        while (dijkstra(s, t)) {
            for (int i = 1; i <= n; i++) {
                h[i] += dis[i];
            }
            T aug = std::numeric_limits<T>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                aug = std::min(aug, e[pre[i]].cap);
            }
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                e[pre[i]].cap -= aug;
                e[pre[i] ^ 1].cap += aug;
            }
            flow += aug;
            cost += aug * h[t];
        }
        return {flow, cost};
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.cost = e[i].cost;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

基环树

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
// 找基环树森林直径和
int n;
    std::cin >> n;
    std::vector<std::vector<std::array<int, 3>>> adj(n + 1);
    int eid = 0;
    for (int i = 1; i <= n; i++) {
        int w, y;
        std::cin >> y >> w;
        adj[i].push_back({y, w, eid});
        adj[y].push_back({i, w, eid});
        eid++;
    }
    std::vector<bool> vis(n + 1), inStack(n + 1), inCycle(n + 1);
    std::vector<i64> dep(n + 1);
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            continue;
        }
        std::vector<int> cir, p(n + 1);
        auto cycle = [&](auto cycle, int x, int fa, int eid) -> void {
            vis[x] = true;
            inStack[x] = true;
            p[x] = fa;
            for (auto [y, w, id] : adj[x]) {
                if (id == eid) {
                    continue;
                }
                if (inStack[y] && cir.empty()) {
                    for (int i = x; i != y; i = p[i]) {
                        cir.push_back(i);
                        inCycle[i] = true;
                    }
                    cir.push_back(y);
                    inCycle[y] = true;
                }
                if (vis[y]) {
                    continue;
                }
                cycle(cycle, y, x, id);
            }
            inStack[x] = false;
        };
        cycle(cycle, i, 0, -1);
        int m = cir.size();
        i64 diameter = 0;
        auto dfs = [&](auto dfs, int x, int fa) -> void {
            int mx1 = 0, mx2 = 0;
            for (auto [y, w, id] : adj[x]) {
                if (y == fa || inCycle[y]) {
                    continue;
                }
                dfs(dfs, y, x);
                diameter = std::max(diameter, dep[x] + dep[y] + w);
                dep[x] = std::max(dep[x], dep[y] + w);
            }
        };
        for (int i = 0; i < m; i++) {
            int x = cir[i];
            dfs(dfs, x, 0);
        }

        std::vector<int> len(m + 1);
        for (int i = 0; i < m; i++) {
            int x = cir[i], y = cir[(i + 1) % m];
            for (auto [z, w, id] : adj[x]) {
                if (z == y) {
                    len[i] = std::max(len[i], w);
                }
            }
        }
        std::vector<i64> pre(2 * m + 1);
        for (int i = 0; i < 2 * m; i++) {
            pre[i + 1] = pre[i] + len[i % m];
        }

        std::vector<i64> a(2 * m);
        for (int i = 0; i < 2 * m; i++) {
            a[i] = dep[cir[i % m]];
        }

        std::deque<int> dq;
        int pos = 0;
        i64 mx = 0;
        for (int i = 1; i < 2 * m; i++) {
            while (pos < i) {
                while (!dq.empty() &&
                       a[pos] - pre[pos] >= a[dq.back()] - pre[dq.back()]) {
                    dq.pop_back();
                }
                dq.push_back(pos);
                pos++;
            }
            while (!dq.empty() && i - dq.front() >= m) {
                dq.pop_front();
            }
            if (!dq.empty()) {
                mx = std::max(mx,
                              a[i] + a[dq.front()] + pre[i] - pre[dq.front()]);
            }
        }
        ans += std::max(mx, diameter);
    }
    std::cout << ans << "\n";

判环

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
// 有向图，可以拓扑排序
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        ans[x] = t++;
        cnt++;
        for (auto y : adj[x]) {
            deg[y]--;
            if (deg[y] == 0) {
                q.push(y);
            }
        }
    }
    if (cnt != n) {
        std::cout << "NO\n";
        return 0;
    }
    std::cout << "YES\n";

// 无向图，将图标记三种状态：未访问，已访问，访问中
 		std::vector<int> ins(n + 1), vis(n + 1);
    auto dfs1 = [&](auto dfs1, int x, int fa) -> void {
        ins[x] = true;
        vis[x] = true;
        for (auto y : adj[x]) {
            if (y == fa) {
                continue;
            }
            if (ins[y]) {
                return;
            }
            if (!vis[y]) {
                dfs1(dfs1, y, x);
            }
        }
        ins[x] = false;
    };
    dfs1(dfs1, 1, 0);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            std::cout << "NO\n";
            return;
        }
    }

n = m 找环

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
std::vector<int> ins(n + 1), vis(n + 1), p(n + 1);
std::vector<int> cir;
auto dfs1 = [&](auto dfs1, int x, int fa) -> void {
    p[x] = fa;
    ins[x] = true;
    vis[x] = true;
    for (auto y : adj[x]) {
        if (y == fa) {
            continue;
        }
        if (ins[y] && cir.empty()) {
            for (int i = x; i != y; i = p[i]) {
                cir.push_back(i);
            }
            cir.push_back(y);
        }
        if (!vis[y]) {
            dfs1(dfs1, y, x);
        }
    }
    ins[x] = false;
};
dfs1(dfs1, 1, 0);
for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
        std::cout << "NO\n";
        return;
    }
}