模板——图论

发表于 2025-11-07 更新于 2026-09-08 分类于 ACM ，模板阅读次数：作者 Pomelorin

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，Tarjan 算法，Prim 算法，Kruskal 算法，欧拉路，Dinic。

Floyd 算法

void floyd(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];
            }
        }
    }
    return;
}

SPFA 算法（慎用）

可用于负权图。时间复杂度可被卡到 \(O(nm)\)。

queue<int> q;

    q.push(x);
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[x] = 0;
    vis[x] = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for (int i = head[now]; i; i = e[i].next) {
            int to = e[i].end;
            if (dis[to] > dis[now] + e[i].len) {
                dis[to] = dis[now] + e[i].len;
                if (!vis[to])
                    q.push(to), vis[to] = 1;
            }
        }
    }

Dijkstra 算法

贪心算法，仅用于正权图。

struct CompareMin {
    bool operator()(const PII &a, const PII &b) const {
        return a.first > b.first; // 对于最小堆，a > b 表示 a 的优先级低于 b
    }
};
priority_queue<PII, vector<PII >, CompareMin> q; 

    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0;
    q.push({dis[s], s});
    while (!q.empty()) {
        auto [tmp, x] = q.top();
        q.pop();
        if (vis[x] == 1) continue;
        vis[x] = 1;
        for (auto [y, w]: e[x]) {
            if (vis[y] == 1)continue;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                q.push({dis[y], y});
            }
        }
    }

Tarjan 算法

强连通分量、缩点属于有向图范畴。
双连通分量、割点、割边属于无向图范畴。

强连通分量

ll dfn[N], low[N], ins[N], stk[N], num = 0, top = 0, scc = 0, bel[N];
vector<ll> e[N];

void tarjan(ll u) {
    dfn[u] = low[u] = (++num);
    ins[u] = 1, stk[++top] = u;
    for (auto v : e[u]) {
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            ll tmp = stk[top];
            bel[tmp] = scc;
            ins[tmp] = 0;
        } while (u != stk[top--]);
    }
}
//注意，一遍tarjan不一定遍历所有点，所以要tarjan所有未访问的点。用dfn[]判断是否访问。

缩点

求完强连通分量后缩点可转化为有向无环图。

void build() {
    for (int now = 1; now <= n; now++) {
        for (int j = big.head[now]; j; j = big.e[j].nxt) {
            int to = big.e[j].end;
            if (bel[now] == bel[to])
                continue;
            small.add(bel[now], bel[to]);
        }
    }
}

边双连通分量

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条点（只能删去一个，不能删 u 或 v）都不能使它们不连通，我们就说 u 和 v 点双连通。

边双连通具有传递性，点双连通不具有传递性。

求边双连通分量的过程实际上就是求强连通分量的过程。

ll n, m;
ll dfn[N], low[N], stk[N], num = 0, top = 0, scc = 0, bel[N];
vector<PII> e[N];
vector<ll> ans[N];

void tarjan(ll u, ll last) {
    dfn[u] = low[u] = (++num);
    stk[++top] = u;
    for (auto [v, id] : e[u]) {
        if (id == (last ^ 1)) // 防止重边现象
            continue;
        if (!dfn[v])
            tarjan(v, id), low[u] = min(low[u], low[v]);
        else
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            ll tmp = stk[top];
            bel[tmp] = scc;
            ans[scc].push_back(tmp);
        } while (u != stk[top--]);
    }
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back({v, i * 2});
        e[v].push_back({u, i * 2 + 1});
    }
    for (ll i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    cout << scc << endl;
    for (ll i = 1; i <= scc; i++) {
        cout << ans[i].size() << " ";
        for (auto j : ans[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
}

点双连通分量

两个点双最多只有一个公共点，且一定是割点。
对于一个点双，它在 DFS 搜索树中 dfn 值最小的点一定是割点或者树根。

我们用栈维护点，当遇到割点或者树根时，将子树内目前不属于其它点双的非割点或在子树中的割点归到一个新的点双。

ll n, m;
ll dfn[N], low[N], stk[N], num = 0, top = 0, scc = 0, bel[N];
vector<ll> e[N], ans[N];

void tarjan(ll u, ll fa) {
    ll sons = 0;
    dfn[u] = low[u] = (++num);
    stk[++top] = u;
    for (auto v : e[u]) {
        if (!dfn[v]) {
            sons++;
            tarjan(v, u), low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                scc++;
                while (stk[top + 1] != v) {
                    bel[stk[top]] = scc;
                    ans[scc].push_back(stk[top--]);
                }
                ans[scc].push_back(u);
            }
        } else if (v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (fa == 0 && sons == 0) {
        ans[++scc].push_back(u); // 特判单点
    }
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (ll i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    cout << scc << endl;
    for (ll i = 1; i <= scc; i++) {
        cout << ans[i].size() << " ";
        for (auto j : ans[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
}

割点

删掉一个节点及其相邻的边，使连通块个数加一。这个节点就是割点。求割点原理是看一个节点的后继是否“返祖”（通过另一条路径访问到这个节点的祖先）。

对于根节点，判断是不是割点很简单——计算其子树数量，如果有 \(2\) 棵及以上的子树，就是割点。对于非根节点，若对于边 \((u,v)\)，如果 \(\text{dfn}_u≤\text{low}_v\)，说明 \(v\) 最早也是在 \(u\) 节点及之后了，此时 \(u\) 就是割点。

void tarjan(int now) {
    int child = 0;
    dfn[now] = low[now] = (++index);
    for (int i = head[now]; i; i = e[i].nxt) {
        int to = e[i].end;
        if (!dfn[to]) {
            tarjan(to);
            low[now] = min(low[now], low[to]);
            if (low[to] >= dfn[now] && now != dad)
                cut[now] = 1;
            if (now == dad)//调用tarjan时： for i: 1->n if !dfn[i] dad=i, tarjan(i)
                child++;
        } else
            low[now] = min(low[now], dfn[to]);
    }
    if (child >= 2 && now == dad)
        cut[now] = 1;
}

割边

删掉一条边，使连通块个数加一。这个边就是割边。

有割点不一定有桥，有桥一定存在割点。
桥一定是割点依附的边。

void tarjan(int now, int dad) //规避儿子访问父亲的情况出现。
{
    int flag = 0; //规避重边
    fa[now] = dad;
    dfn[now] = low[now] = (++index);
    for (int i = head[now]; i; i = e[i].nxt) {
        int to = e[i].end;
        if (!dfn[to]) {
            tarjan(to, now);
            low[now] = min(low[now], low[to]);
            if (low[to] > dfn[now])
                cut[to] = 1; // 表示 (to, fa[to]) 是桥
        } else {
            if (to != dad || flag) {
            	low[now] = min(low[now], dfn[to]);
            } else {
                flag = 1;
            }
        }
    }
}

Prim 算法

跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。堆优化的方式类似 Dijkstra 的堆优化。

int g[N][N], v[N], d[N]; //边，访问标记，距离当前已加入的点集的距离
void prim() {
    for (int i = 1; i <= n; i++)
        d[i] = g[1][i];
    v[1] = 1;
    for (int i = 1; i <= n - 1; i++) {//寻找 n-1 轮
        int to = -1, mn = inf;
        for (int j = 1; j <= n; j++)
            if (!v[j] && d[j] < mn)
                to = j, mn = d[j];
        if (to < 0)
            return;
        ans += mn, v[to] = 1;//成为最小生成树的树边
        for (int j = 1; j <= n; j++)
            if (!v[j] && d[j] > g[to][j])
                d[j] = g[to][j];
    }
    return;
}

Kruskal 算法

从小到大加入边，是个贪心算法。需要并查集维护。

最小瓶颈生成树即对于图 G 中的生成树上最大的边权值在所有生成树中最小。最小生成树是它的子集。

最小瓶颈路问题是指在一张无向图中，询问一个点对 \((u,v)\)，需要找出从 u 到 v 的一条简单路径，使路径上所有边中边权最大值最小。最小生成树上 u 到 v 的路径一定是 u 到 v 的最小瓶颈路之一。

void kruskal() {
    int num = 0, ru, rv;
    sort(e + 1, e + cnt + 1, cmp);
    for (int i = 1; i <= m; i++) {
        ru = ufds.find(e[i].u), rv = ufds.find(e[i].v);
        if (ru == rv)
            continue;
        ans += e[i].len;//成为最小生成树的树边
        ufds.merge(ru, rv);
        if (++num == n - 1)
            break;
    }
}

欧拉路

我们先结合定理进行分析：

如果是求有没有欧拉回路：判断是有向图还是无向图，若为有向图，所有顶点出、入度相等。若为无向图，则没有奇度顶点。
如果是求有没有欧拉通路：判断是有向图还是无向图，若为有向图，所有顶点的出度与入度相等或者除两个顶点外其余顶点的出度等于入度（另外两个顶点一个为入度比出度大一为起点，另外一个反之为终点）。若为无向图，仅有两个奇度顶点或者没有奇度顶点。

这里以有向图为例，求是否存在欧拉回路或者欧拉通路。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e5 + 10, inf = 1e17;

vector<PII> e[N];
vector<ll> ans;
ll n, m, cur[N], in[N], out[N], vis[N * 2], st = 0, ed = 0;

bool cmp(PII a, PII b) {
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

void dfs(ll now) {
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        if (!vis[e[now][i].second]) {
            vis[e[now][i].second] = 1;
            dfs(e[now][i].first);
        }
    }
    ans.push_back(now);
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back({v, i});
        in[v]++;
        out[u]++;
    }
    for (ll i = 1; i <= n; i++) {
        sort(e[i].begin(), e[i].end(), cmp);
        if (abs(in[i] - out[i]) > 1) {
            cout << "No" << endl;
            return;
        }
        if (out[i] - in[i] == 1) {
            if (st) {
                cout << "No" << endl;
                return;
            }
            st = i;
        }
        if (in[i] - out[i] == 1) {
            if (ed) {
                cout << "No" << endl;
                return;
            }
            ed = i;
        }
    }
    if (!st) {
        st = 1;
    }
    dfs(st);
    if (ans.size() != m + 1) {
        cout << "No" << endl;
        return;
    }
    for (auto i = ans.rbegin(); i != ans.rend(); ++i) {
        cout << *i << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

如果以无向图为例，求是否存在欧拉回路或者欧拉通路。

void dfs(ll now) {
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        if (!vis[e[now][i].second]) {
            vis[e[now][i].second] = 1;
            vis[e[now][i].second ^ 1] = 1;
            dfs(e[now][i].first);
        }
    }
    ans.push_back(now);
}

for (ll i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back({v, i * 2});//一定要注意 2 3 是一对，4 5 是一对...
    e[v].push_back({u, i * 2 + 1});
    du[u]++;
    du[v]++;
    minn = min({minn, u, v});
}

Dinic

重点在于建模。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 2e2 + 10, inf = 1e17;

struct edge {
    ll to, val, rev;
};

ll dinicn, m, s, t, cur[N], lvl[N];
vector<edge> e[N];

ll bfs() {
    for (ll i = 1; i <= dinicn; i++) {
        lvl[i] = 0;
        cur[i] = 0;
    }
    queue<ll> q;
    q.push(s);
    lvl[s] = 1;
    while (!q.empty()) {
        ll now = q.front();
        q.pop();
        for (auto [to, val, rev] : e[now]) {
            if (val > 0 && !lvl[to]) {
                q.push(to);
                lvl[to] = lvl[now] + 1;
                if (to == t)
                    return 1;
            }
        }
    }
    return 0;
}

ll dfs(ll now, ll flow) {
    if (now == t) {
        return flow;
    }
    ll res = 0;
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        auto [to, val, rev] = e[now][i];
        if (val > 0 && lvl[to] == lvl[now] + 1) {
            ll f = dfs(to, min(val, flow));
            if (f == 0) {
                lvl[to] = 0;
            }
            e[now][i].val -= f;
            e[to][rev].val += f;
            res += f;
            flow -= f;
            if (flow == 0) {
                return res;
            }
        }
    }
    return res;
}

void add(ll a, ll b, ll c) {
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

void solve() {
    ll ans = 0;
    cin >> dinicn >> m >> s >> t;
    for (ll i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].push_back((edge){v, w, e[v].size()});
        e[v].push_back((edge){u, 0, e[u].size() - 1});
    }
    while (bfs()) {
        ans += dfs(s, inf);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}