Skip to content
TechMind

图论

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
struct SCC
{
    int n, now, cnt;
    vector<vector<int>> ver;
    vector<int> dfn, low, col, S;

    SCC(int n) : n(n), ver(n + 1), low(n + 1)
    {
        dfn.resize(n + 1, -1);
        col.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++;
        S.push_back(x);
        for (auto y : ver[x])
        {
            if (dfn[y] == -1)
            {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if (col[y] == -1)
                low[x] = min(low[x], dfn[y]);
        }
        if (dfn[x] == low[x])
        {
            int pre;
            cnt++;
            do
            {
                pre = S.back();
                col[pre] = cnt;
                S.pop_back();
            } while (pre != x);
        }
    }

    tuple<int, vec<vec<int>>, vec<int>> work()
    {                                // [cnt 新图的顶点数量]
        for (int i = 1; i <= n; i++) // 避免图不连通
            if (dfn[i] == -1)
                tarjan(i);

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

点双连通分量🧀

 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
struct VDCC
{
    int n;
    vector<vector<int>> ver, col;
    vector<int> dfn, low, S;
    int now, cnt;
    vector<char> point; // 记录是否为割点

    V_DCC(int n) : n(n)
    {
        ver.resize(n + 1);
        dfn.resize(n + 1);
        low.resize(n + 1);
        col.resize(2 * n + 1);
        point.resize(n + 1);
        S.clear();
        cnt = now = 0;
    }
    void add(int x, int y)
    {
        if (x == y)
            return; // 手动去除重边
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void tarjan(int x, int root)
    {
        low[x] = dfn[x] = now++;
        S.push_back(x);
        if (x == root && !ver[x].size())
        { // 特判孤立点
            ++cnt;
            col[cnt].push_back(x);
            return;
        }

        int flag = 0;
        for (auto y : ver[x])
        {
            if (!dfn[y])
            {
                tarjan(y, root);
                low[x] = min(low[x], low[y]);
                if (dfn[x] <= low[y])
                {
                    flag++;
                    if (x != root || flag > 1)
                        point[x] = 1; // 标记为割点
                    int pre = 0;
                    cnt++;
                    do
                    {
                        pre = S.back();
                        col[cnt].push_back(pre);
                        S.pop_back();
                    } while (pre != y);
                    col[cnt].push_back(x);
                }
            }
            else
                low[x] = min(low[x], dfn[y]);
        }
    }
    pair<int, vector<vector<int>>> work()
    { // [新图的顶点数量, 新图]
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i, i);
        vector<vector<int>> adj(cnt + 1);
        for (int i = 1; i <= cnt; i++)
        {
            if (!col[i].size()) // 注意，孤立点也是 V-DCC
                continue;
            for (auto j : col[i])
                if (point[j])
                { // 如果 j 是割点
                    adj[i].push_back(point[j]);
                    adj[point[j]].push_back(i);
                }
        }
        return {cnt, adj};
    }
};

边双连通分量🧀

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

    EDCC(int n) : n(n), ver(n + 1), low(n + 1)
    {
        dfn.resize(n + 1, -1);
        col.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)
            {
                bridge.insert({x, y});
                tarjan(y, x);
                low[x] = min(low[x], low[y]);
            }
            else if (col[y] == -1 && dfn[y] < dfn[x])
            {
                bridge.insert({x, y});
                low[x] = min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x])
        {
            int pre;
            cnt++;
            do
            {
                pre = S.back();
                col[pre] = cnt;
                S.pop_back();
            } while (pre != x);
        }
    }
    auto work()
    {                                // [cnt 新图的顶点数量, bridge 全部割边]
        for (int i = 1; i <= n; i++) // 避免图不连通
            if (dfn[i] == -1)
                tarjan(i, 0);

        vector<int> siz(cnt + 1);         // siz 每个边双中点的数量
        vector<vector<int>> adj(cnt + 1); // adj 新图
        for (int i = 1; i <= n; i++)
        {
            siz[col[i]]++;
            for (auto j : ver[i])
            {
                int x = col[i], y = col[j];
                if (x != y)
                    adj[x].push_back(y);
            }
        }
        return tuple{cnt, adj, col, siz};
    }
};

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
void cold_beans()
{
    int n, m, s;
    cin >> n >> m >> s;
    vec<vec<int>> g(n + 1), st(20, vec<int>(n + 1));
    vec<int> dep(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    auto dfs = [&](this auto &&dfs, int u, int fa, int d) -> void
    {
        st[0][u] = fa;
        dep[u] = d;
        for (auto v : g[u])
        {
            if (v == fa)
                continue;
            dfs(v, u, d + 1);
        }
    };
    dfs(s, 0, 1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            st[i][j] = st[i - 1][st[i - 1][j]];
    auto lca = [&](int a, int b) -> int
    {
        if (dep[a] < dep[b])
            swap(a, b);
        int wt = dep[a] - dep[b];
        for (int i = 0; i < 20; i++)
            if (wt & 1 << i)
                a = st[i][a];
        if (a == b)
            return a;
        for (int i = 19; i >= 0; i--)
        {
            if (dep[a] > 1 << i && st[i][a] != st[i][b])
                a = st[i][a], b = st[i][b];
        }
        return st[0][a];
    };
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
}

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
void cold_beans()
{
    int n, m, s;
    cin >> n >> m >> s;
    vec<vec<int>> g(n + 1);
    vec<int> ans(m + 1);
    vec<char> vis(n + 1);
    vec<vec<aii>> q(n + 1);
    DSU dsu(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        q[a].pb({b, i});
        q[b].pb({a, i});
    }
    auto dfs = [&](this auto &&dfs, int u, int fa) -> void
    {
        vis[u] = 1;
        for (auto v : g[u])
        {
            if (v == fa)
                continue;
            dfs(v, u);
            dsu.merge(v, u);
        }
        for (auto &[v, num] : q[u])
            if (vis[v])
                ans[num] = dsu.get(v);
    };
    dfs(s, 0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << endl;
}

Hierholzer🧀

有向图🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
vector<int> ans; // 有向图，倒序输出ans得到路径。如果需要字典序最小的路径,把g中的vec改pq，back改top,ppb改pop

auto dfs = [&](this auto &&dfs, int u) -> void
{
    while (!g[u].empty())
    {
        int v = g[u].back();
        g[u].pop_back();
        dfs(v);
    }
    ans.pb(u);
};

无向图🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
//如果不需要字典序最小可以把pq换成vec
vector<char> vis(m + 1);
vector<priority_queue<aii, vector<aii>, greater<aii>>> g(501);
vector<int> ans;

auto dfs = [&](this auto &&dfs, int u) -> void
{
    while (!g[u].empty())
    {
        auto [v, i] = g[u].top();
        g[u].pop();
        if (!vis[i])
        {
            vis[i] = 1;
            dfs(v);
        }
    }
    ans.push_back(u);
};

Dijkstra🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> dis(n + 1, inf);
vector<char> vis(n + 1);
priority_queue<aii, vector<aii>, greater<aii>> q;
int s = 1;
q.push({0, s});
dis[s] = 0;
while (!q.empty())
{
    auto [w, v] = q.top();
    q.pop();
    if (vis[v])
        continue;
    vis[v] = 1;
    for (auto &[nv, nw] : g[v])
    {
        if (dis[nv] > dis[v] + nw)
        {
            dis[nv] = dis[v] + nw;
            q.push({dis[nv], nv});
        }
    }
}

SPFA🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<int> dis(n + 1, inf), vis(n + 1);
queue<int> q;
dis[s] = 0;
q.push(s);
while (!q.empty())
{
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (auto [v, w] : g[u])
        if (dis[u] + w < dis[v])
        {
            dis[v] = dis[u] + w;
            if (!vis[v])
            {
                vis[v] = 1;
                q.push(v);
            }
        }
}

HK🧀

 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
struct HK
{
    int n, m;
    vec<vec<int>> g;
    vec<int> ti, rec;
    HK(int _n, int _m) : n(_n), m(_m)
    {
        g.resize(n + 1);
        ti.resize(n + 1);
        rec.resize(m + 1);
    }

    bool dfs(int u, int t)
    {
        if (ti[u] == t)
            return 0;
        ti[u] = t;
        for (auto v : g[u])
        {
            if (!rec[v] || dfs(rec[v], t))
            {
                rec[v] = u;
                return 1;
            }
        }
        return 0;
    }

    void add(int x, int y)
    {
        g[x].pb(y);
    }

    int work()
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += dfs(i, i);
        return ans;
    }
};

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct twosat
{
    vector<vector<int>> g;
    vector<int> dfn, low, col, st;
    vector<short> ans;
    int n, cur, cnt;

    twosat(int _n)
    {
        n = _n;
        g.assign(2 * n + 1, {});
        cur = cnt = 0;
        dfn.assign(2 * n + 1, -1);
        low.assign(2 * n + 1, -1);
        col.assign(2 * n + 1, -1);
        ans.assign(n + 1, 0);
    }

    void add(int u, bool f1, int v, bool f2)
    {
        // idx小的点表示真，idx大的点表示假
        g[n * f1 + u].pb(n * (f2 ^ 1) + v);
        g[n * f2 + v].pb(n * (f1 ^ 1) + u);
    }

    void tarjan(int u)
    {
        dfn[u] = low[u] = ++cur;
        st.push_back(u);
        for (auto v : g[u])
            if (dfn[v] == -1)
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (col[v] == -1)
                low[u] = min(low[u], dfn[v]);
        if (dfn[u] == low[u])
        {
            int pos = 0;
            cnt++;
            do
            {
                pos = st.back();
                st.pop_back();
                col[pos] = cnt;
            } while (pos != u);
        }
    }

    bool work()
    {
        for (int i = 1; i <= 2 * n; i++)
            if (dfn[i] == -1)
                tarjan(i);
        for (int i = 1; i <= n; i++)
        {
            if (col[i] == col[i + n])
                return false;
            ans[i] = col[i] < col[i + n];
        }
        return true;
    }

    vector<short> answer() { return ans; };
};