模板——图论

发表于 分类于 ， 阅读次数： 作者 Pomelorin

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，强连通分量，Prim 算法，Kruskal 算法，Dinic 最大流，欧拉路。

Floyd 算法

1
2
3
4
5
6
7
8
9
10
11
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)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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});
            }
        }
    }

强连通分量

求强连通分量

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
dfn [N] //时间戳。
low [N] //一个节点向子树方向能够追溯到的最早的时间戳。
ins [N] //是否在栈中
stk [N] //手工栈。注意，这个栈与系统栈不同。
bel [N] //一个节点从属于哪个强连通分量。
top = 0 //栈的顶部指针。
scc = 0 //强连通分量个数。
index = 0 //用来戳时间戳。

void tarjan(int now) {
    dfn[now] = low[now] = (++index); //戳时间戳
    ins[now] = 1;
    stk[++top] = now; //打上入栈标记，入栈
    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]);
            //进行dfs，并根据前文求low_u。
        else if (ins[to])
            low[now] = min(low[now], dfn[to]);
        //已经在栈中且访问过了，回溯，并根据前文求low_u。
    }
    if (dfn[now] == low[now]) //强连通分量增加了
    {
        scc++;
        do {
            int tmp = stk[top];
            ins[tmp] = 0;
            bel[tmp] = scc;
        } while (now != stk[top--]); //弹栈
    }
}
//注意，一遍tarjan不一定遍历所有点，所以要tarjan所有未访问的点。用dfn[]判断是否访问。

缩点

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

1
2
3
4
5
6
7
8
9
10
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]);
        }
    }
}

割点

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)// 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;
}

割边

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

  1. 有割点不一定有桥，有桥一定存在割点。
  2. 桥一定是割点依附的边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void tarjan(int now, int 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[now] = 1;
        } else if (to != dad) {
            low[now] = min(low[now], dfn[to]);
        }
    }
}

拓扑排序

对于有向无环图。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
//拓扑排序

vector<int> m[10005]; //有向图
int b[10005]; //入度

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (x != 0) {
            m[i].push_back(x);
            b[x]++;
            cin >> x;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int c: m[x]) {
            b[c]--;
            if (b[c] == 0) {
                q.push(c);
            }
        }
        cout << x << ' ';
    }
    return 0;
}

Prim 算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 的最小瓶颈路之一。

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

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

using namespace std;
#define PII pair<int,int>
#define TIII tuple<int,int,int>
#define int long long
//网络流(dinic)

const int N = 205, M = 5005;
vector<TIII > e[M]; //点，边权，反向边编号
int lev[N], cur[N], ans; //bfs分层，弧优化，最大流
int n, m, s, t;

int bfs() {
    for (int i = 0; i <= n; i++)lev[i] = -1, cur[i] = 0;
    queue<int> q;
    q.push(s);
    lev[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto [y, w, temp2]: e[x]) {
            if (lev[y] == -1 && w > 0) {
                lev[y] = lev[x] + 1;
                q.push(y);
            }
        }
    }
    return lev[t] != -1;
}

int dfs(int x, int flow) {
    if (x == t) {
        return flow;
    }
    for (int &i = cur[x]; i < e[x].size(); i++) {
        auto &[y, w, rev] = e[x][i];
        if (lev[y] == lev[x] + 1 && w > 0) {
            int lim = dfs(y, min(flow, w));
            if (lim > 0) {
                w -= lim;
                std::get<1>(e[y][rev]) += lim;
                return lim;
            }
        }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        e[x].push_back({y, w, e[y].size()});
        e[y].push_back({x, 0, e[x].size() - 1});
    }
    while (bfs()) {
        while (1) {
            int x = dfs(s, 4e18);
            if (x == 0)break;
            ans += x;
        }
    }
    cout << ans;
    return 0;
}

欧拉路

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

  • 如果是求有没有欧拉回路：判断是有向图还是无向图，若为有向图，所有顶点出、入度相等。若为无向图，则没有奇度顶点。

  • 如果是求有没有欧拉通路：判断是有向图还是无向图，若为有向图，所有顶点的出度与入度相等或者除两个顶点外其余顶点的出度等于入度。若为无向图，仅有两个奇度顶点或者没有奇度顶点。

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

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
//欧拉路

//此题是无向图求欧拉通路
//思路是从奇数点开始(如果存在)dfs，然后在回溯的时候再把边加进去
struct edge {
    int next;
    int b = 1;
    int r; //反向边下标(?
    int num; //对应边的编号
};

const int N = 2e5;
vector<edge> e[2 * N + 5];
int cur[2 * N + 5];
vector<int> ans;

void dfs(int x,int num) {
    //点编号和边编号
    for (int &i = cur[x]; i < e[x].size(); i++) {
        auto &ex = e[x][i];
        if (ex.b == 1) {
            ex.b = 0;
            e[ex.next][ex.r].b = 0;
            dfs(ex.next, ex.num);
        }
    }
    ans.push_back(num);
    return;
}

void solve() {
    int n;
    cin >> n;
    int cnt = 1;
    map<int,int> m1;
    map<int,int> m2;
    int d[2 * n + 5] = {};
    ans.clear();
    for (int i = 0; i <= 2 * n + 5; i++)e[i].clear(), cur[i] = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        if (m1[x] == 0)m1[x] = cnt++;
        if (m2[y] == 0)m2[y] = cnt++;
        x = m1[x];
        y = m2[y];
        e[x].push_back({y, 1, (int) e[y].size(), i});
        e[y].push_back({x, 1, (int) e[x].size() - 1, i});
        d[x]++;
        d[y]++;
    }
    //1~cnt-1
    int sum = 0;
    int st = 1;
    for (int i = 1; i < cnt; i++) {
        if (d[i] % 2 == 1) {
            sum++;
            st = i;
        }
    }
    if (sum == 0 || sum == 2) {
    } else {
        cout << "NO";
        return;
    }
    dfs(st, 0);
    if (ans.size() == n + 1) {
        //判断是不是连通
        cout << "YES" << endl;
        for (int i = 0; i < ans.size() - 1; i++) {
            cout << ans[i] << ' ';
        }
    } else {
        cout << "NO";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}