图论模板

包括了一些简单的图论内容,不含网络流

树与图的存储

邻接矩阵:mp[a][b]mp[a][b] 存储边 aba \rightarrow b

邻接表:

1
2
3
4
5
6
7
8
9
10
11
12
int head[MAXN];//表头
int tot;//边的总数
struct EDGE {
int to, next, val;
}edge[MAXM];
void add_edge(int from,int to,int val) {
//添加一条边
edge[++tot].to = to; edge[tot].val = val; edge[tot].next = head[from]; head[from] = tot;
}
//初始化
tot = 0;
memset(head, 0, sizeof head);

树与图的遍历

时间复杂度 O(n+m)O(n+m) nn 表示点数 ,mm 表示边数

深度优先遍历:

1
2
3
4
5
6
7
8
int vis[MAXN];//标记某个点有没有被遍历过
void dfs(int now) {
vis[now] = 1;
for(int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (!vis[to]) dfs(to);
}
}

宽度优先遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int vis[MAXN];//标记某个点有没有被遍历过
void bfs(int s) {
queue<int> q;
vis[s] = 1;//标记起点
q.push(s);
while (!q.empty()) {
int now=q.front(); q.pop();
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (!vis[to]) {
vis[to] = true;//表示to已经被遍历过
q.push(to);
}
}
}
}

树的直径

树形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
int n, ans;
const int N = 1e4 + 10;
int f[N];
struct node {
int v;int w;
};
vector<node> ve[N];

int dfs(int u, int pre) {
int dis = 0;
int d1 = 0, d2 = 0;
for (node i : ve[u]) {
if (i.v == pre) continue;
int d = dfs(i.v, u) + i.w;
dis = max(dis, d);
if (d >= d1) {
d2 = d1, d1 = d;
}
else if (d > d2) d2 = d;
}

ans = max(ans, d1 + d2);
return dis;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
int u, v, w;
for (int i = 1; i < n; ++i) {
cin >> u >> v >> w;
ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
}

dfs(1, 0);
printf("%d\n", ans);

return 0;
}

两次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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n;
const int N = 1e4 + 10;
int dis[N];
struct node {
int v;int w;
};
vector<node> ve[N];

void dfs(int u, int pre) {
for (node i : ve[u]) {
if (i.v == pre) continue;
dis[i.v] = dis[u] + i.w;
dfs(i.v, u);
}
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
int u, v, w, t, res;
for (int i = 1; i < n; ++i) {
cin >> u >> v >> w;
ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
}
dis[1] = 0;
dfs(1, 0);
t = -1, res = -1;
for (int i = 1; i <= n; ++i) {
if (dis[i] > res) {
res = dis[i], t = i;
}
}
dis[t] = 0;
dfs(t, 0);
t = -1, res = -1;
for (int i = 1; i <= n; ++i) {
if (dis[i] > res) {
res = dis[i], t = i;
}
}
printf("%d\n", res);

return 0;
}


树的中心

在树中找到一个点,使得该点与树中其他点的最远距离最近

树形DP

进行两次树形dp
以任意结点为根,对于结点i来说,离它最远的点有2种可能,一是向下走遇到最远点(此时最远点为i的孩子);
二是向上走(可能先向上走再向下走)遇到最远点(此时最远点不是它的孩子)。

  1. down[i]: 以i为两条路径的最高点,求最长路径和次长路径,以及最长路径所在的子节点;
  2. up[i]: 从i开始向上走,离最远点的距离;
  3. f[i] = max(down[i], up[i]);
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
const int N = 1e4 + 10;
struct dist {
int d1, d2, inx;
};
dist down[N];
struct node {
int v, w;
};
vector<node> ve[N];
int up[N], f[N];

int dfs(int cur, int pre) {
int d1 = 0, d2 = 0, inx = 0;
for (node i : ve[cur]) {
if (i.v == pre) continue;
int d = dfs(i.v, cur) + i.w;
if (d > d1) {
inx = i.v, d2 = d1, d1 = d;
}
else if (d > d2) {
d2 = d;
}
}
down[cur] = dist{d1, d2, inx};
return d1;
}

void dp(int cur, int pre, int d) {
int inx = down[pre].inx, d1 = down[pre].d1, d2 = down[pre].d2;
up[cur] = up[pre] + d;
if (inx == cur) {
up[cur] = max(up[cur], d2 + d);
}
else {
up[cur] = max(up[cur], d1 + d);
}
f[cur] = max(up[cur], down[cur].d1);
for (node i : ve[cur]) {
if (i.v == pre) continue;
dp(i.v, cur, i.w);
}
}

int main(void) {
int u, v, w;
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
cin >> u >> v >> w;
ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
}

dfs(1, 0);
dp(1, 0, 0);

int res = 1e9 + 10;
for (int i = 1; i <= n; ++i) {
res = min(res, f[i]);
}
cout << res << endl;

return 0;
}


图的直径

floydfloydfloydfloyd 能求出任意两点间的距离,取最值就行。

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
ll n, m;
ll dis[505][505];
void init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) dis[i][j] = 0;
else dis[i][j] = INF;
}

void solve() {
n = read(), m = read();
init();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
dis[u][v] = 1;
dis[v][u] = 1;
}
ll ans = 0;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans = max(ans, dis[i][j]);
printf("%lld\n", ans);

}

最小环相关

DFS树求无向图最小环

将图看成一颗“树”,利用深度和 dfsdfs 遍历树的性质求解。正常 dfsdfs 遍历时,总是由深度小的点往深度大的点更新,而环的存在就导致可能在某一点能够回到其祖先节点。这样环的长度即为 depth[now]depth[to]+1depth[now] - depth[to] + 1

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
int n, m;
int depth[MAXN];//点的深度
int fa[MAXN];//前驱
int mn = INF;//最小环长度
int start = 0;//打印环用

void dfs(int now, int pre) { //求解最小环问题
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (to == pre) continue;
if (depth[to] != 0 && depth[now] - depth[to] + 1 < mn) {
//这条边连向了祖先节点,说明是个环。深度跨距表示环的长度,说明当前小于最小环
if (depth[now] - depth[to] + 1 < 0) continue; //由于是无向边+树的遍历,这种情况是存在的
mn = depth[now] - depth[to] + 1;
start = now;
}
else if(!depth[to]) {
fa[to] = now;
depth[to] = depth[now] + 1;
dfs(to, now);
}
}
}

void output() { //打印最小环
printf("%d\n", mn); //先输出最小环的长度
int now = start;
for (int i = 1; i <= mn; i++) {
printf("%d ", now);
now = fa[now];
}
}

void solve() {
depth[1] = 1; //初始化
dfs(1, 0);
output();
}

floyd求无向图最小环

在每次以顶点 kk 为中间点求得完最短路后,再循环更新两点间的最小回路。

最小环权值数组 dis[i][j]dis[i][j] ,已知的权值数组 a[i][j]a[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//初始化
#define INF 0x3f3f3f3f
int ans = INF;
memset(dis, 0x3f, sizeof(dis));
memset(a, 0x3f, sizeof(a));

//输入图中两点边权a[i][j]

for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++)
ans = min(ans, dis[i][j] + a[i][k] + a[k][j]);
//答案为i到j的最短路径权值加上j到k的边权和i到k的边权
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
//更新i到j的最短路径
}

并查集求有向图最小环长度

当并查集找祖先找到自己的时候,说明出现了环。可以在查找祖先的同时记录下遍历的次数,当最后找到自己的时候与当前最小环的长度进行比较,看是否需要更新。注意: 这条边不用相连,否则会进入死循环。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
int ans = 0x3f3f3f3f;//最小环的个数
int f[MAXN];
ll n;
int cnt;
int findx(int x, int &cnt) {
cnt++;
if (x == f[x]) return x;
else return findx(f[x], cnt);
}

void solve() {
cin >> n;
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= n; i++) {
int temp;
cnt = 0;
cin >> temp;
int goal = findx(temp, cnt);
if (goal == i) {
ans = min(ans, cnt);
}
else f[i] = temp;
}
cout << ans << endl;
}

int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
return 0;
}

有向带权图的最小环

枚举每一个点作为起点,在松弛完起点所有的出边后把起点的 disdis 重置为 INFINFvisitvisit 重置为 falsefalse 。之后再扫到该起点时该起点的 disdis 为最小环。堆优化后复杂度为 O(n(n+m)logn)O(n(n+m)logn)

这是另一种做法:

根据题目的特殊要求,当存在一个环的边权和小于等于c是返回1否则返回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
int dij(int s) {
for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0;
dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({dis[s], s});
while (q.size()) {
int now = q.top().second;
q.pop();
if (vis[now]) continue;
vis[now] = 1;
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
ll val = edge[i].val;
if (to == s && dis[now] + val <= c) return 1;
if (dis[to] > dis[now] + val) {
dis[to] = dis[now] + val;
q.push({dis[to], to});
}
}
}
return 0;
}

for (int i = 1; i <= n; i++) {
int tmp = dij(i);
if (tmp == 1) {
ans++;
break;
}
}

正常求最小环的话应该遍历起始点,然后每次找到一个环就和当前的就好了

拓扑排序

时间复杂度 O(n+m)O(n+m)nn 表示点数,mm 表示边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int indgr[MAXN];//记录有向图的入度数
void topu() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (!indgr[i])//将入度数为0的点推入队列
q.push(i);
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
//进行相关操作
if (--indgr[to] == 0)
q.push(to);
}
}
}

最短路相关

朴素 dijkstra 算法

时间复杂度 O(n2+m)O(n^2+m)nn 表示点数,mm 表示边数

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
#define INF 0x3f3f3f3f
int mp[MAXN][MAXN];//存储每条边
int dis[MAXN];//存储一号点到每个点的最短距离
int vis[MAXN];//存储每个点的最短路是否已经确定
//求一号点到n号点的最短距离,如果不存在返回-1

void init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) mp[i][j] = 0;
else mp[i][j] = INF;
}

int dij(int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for(int i = 0; i < n - 1; i++) {
int t = -1;//在还未确定最短路的点中,寻找距离最小的点
for(int j = 1; j <= n; j++)
if(!vis[j] && (t == -1 || dis[t] > dis[j]))
t=j;

for (int j = 1; j <= n; j++)
dis[j] = min(dis[j], dis[t] + mp[t][j]);//用t更新其他点的最短距离

vis[t] = 1;
}
if (dis[n] == INF) return -1;
return dis[n];
}

堆优化dijkstra

时间复杂度 O(mlogn)O(mlogn) , nn 表示点数 , mm 表示边数

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
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
int n;//点的数量
int dis[MAXN];//存储所有点到一号点的距离
int vis[MAXN];//存储每个点的最短距离是否已经确定

//求一号点到n号点的最短距离,如果不存在,则返回-1
int dij(int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<pii> q;
q.push({dis[s], s});
while (!q.empty()) {
int now = q.top().second; q.pop();
if (vis[now]) continue;
vis[now] = 1;
for(int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
int val = edge[i].val;
if(dis[to] > dis[now] + val) {
dis[to] = dis[now] + val;
q.push({-dis[to], to});
}
}
}
if(dis[n] == INF) return -1;
return dis[n];
}

超级源点与超级终点

多用于图中有多个源点和多个终点的情况

如果有多个起点,跑 kk 遍算法很容易超时,这时建立一个超级源点,与所有起点连一条权值为 00 的边,单单对这个点进行操作。超级终点也是如此

最短路方案计数问题

在松弛里做一些操作。如果dis[to]==now+val,则方案数累加;如果dis[to]>dis[now]+val,则用新的方案替代原先的方案

求次短路

在松弛里做一些操作。如果可以更新最短路,则更新最短路,原最短路变为次短路;若可更新次短路,则更新次短路。

bellman-ford

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
ll n, m;
struct node {
ll val;
int u, v;
}a[MAXM];
ll dis[MAXN];

void solve() {
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
ll w = read();
a[i] = {-w, u, v};
}
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 1; i <= n; i++) {
for (int i = 1; i <= m; i++) {
ll val = a[i].val;
int u = a[i].u;
int v = a[i].v;
if (dis[v] > dis[u] + val) {
dis[v] = dis[u] + val;
}
}
}
ll ans = dis[n];
for (int i = 1; i <= m; i++) {
ll val = a[i].val;
int u = a[i].u;
int v = a[i].v;
if (dis[v] > dis[u] + val) {
dis[v] = dis[u] + val;
}
}
if (dis[n] != ans) //n号节点的负环中
puts("inf");
else
printf("%lld\n", -ans);
}
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
int n, m;       // n表示点数,m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离

struct Edge {
// 边,a表示出点,b表示入点,w表示边的权重
int a, b, w;
}edges[M];

// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}

if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}

SPFA

时间复杂度 平均情况下 O(m)O(m) ,最坏情况下 O(nm)O(nm)nn 表示点数 ,mm 表示边数

ssnn 的最短距离,如果无法走到输出 1-1

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
#define INF 0x3f3f3f3f
int n;//总点数
int dis[MAXN];//存储每个点到s的最短距离
int vis[MAXN];//存储每个点是否在队列中
int spfa(int s) {
queue<int> q;
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0; vis[s] = 1; q.push(s);
while (!q.empty()) {
int now = q.front(); q.pop();
vis[now] = 0;
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
int val = edge[i].val;
if (dis[to] > dis[now] + val) {
dis[to] = dis[now] + val;
if (!vis[to]){
//如果队列中已存在to,则不需要将to重复插入
q.push(to);
vis[to] = 1;
}
}
}
}
if (dis[n] == INF) return -1;
return dis[n];
}

最长路

SPFA可以处理负权边,所以还可以较简单的求最长路。一开始将dis重置为负无穷大,松弛操作时候的再取反即可。或者一开始直接将所有边权取反,跑一遍SPFA的最短路模板

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
29
30
31
32
#define INF 0x3f3f3f3f
int n;//总点数
int dis[MAXN];//存储每个点到s的最短距离
int vis[MAXN];//存储每个点是否在队列中
int cnt[MAXN];//存储1到x的最短路中经过的点数
bool spfa(int s) {
//如果存在负环,返回true;否则返回false
queue<int> q;
//不需要初始化dis数组
for (int i = 1; i <= n; i++) {
q.push(i);
vis[i] = 1;
}
while (!q.empty()) {
int now = q.front(); q.pop();
vis[now] = 0;
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
int val = edge[i].val;
if (dis[to] > dis[now] + val) {
dis[to] = dis[now] + val;
cnt[to] = cnt[now] + 1;
if (cnt[to] >= n) return true;//一条路径上包含至少n个点说明存在环
if (!vis[to]) {
q.push(to);
vis[to] = 1;
}
}
}
}
return false;
}

SPFA判正环

同样,SPFA判正环只需将松弛操作的符号反一下即可。

差分约束系统

如果一个系统由 nn 个变量和 mm 个不等式组成,并且这 mm 个不等式均为 xixja[k]x_i - x_j \leq a[k] 的形式,这样的系统成为 差分约束

求最大值,跑最短路;求最小值,跑最长路。

最短路求完后任意三角关系满足:dis[to]dis[now]+mp[now][to]dis[to] \leq dis[now] + mp[now][to]

最长路求完后任意三角关系满足:dis[to]dis[now]+mp[now][to]dis[to]\geq dis[now] + mp[now][to]

nowtonow \rightarrow to 连一条权值为 mp[now][to]mp[now][to] 的边。

需要提前通过乘以负号等操作使得所有不等式 符号相同 以进行最短/长路的进一步操作。只能用 SPFASPFA

有唯一解 是最简单的一种情况,源点 SS 到终点 EE 之间存在最短路。

如果源点 SS 到终点 EE 不存在最短路,即存在 负环 ,就可以表示为方程的 无解情况

如果源点 SS 根本无法到达终点 EE ,即 dis[E]=INFdis[E]=INF,表示 SSEE 之前不存在约束关系,表示为方程的 多解情况

  1. 求差值的最大值,全部转化为 xyzx-y \leq z 这种格式;求差值的最小值,全部转化为 xyzx-y \geq z 这种形式
  2. 如果有形如 xy=zx-y=z 的形式,将其变化成两个不等式:xyzx-y \leq zxyzx-y \geq z
  3. 如果有形如 xy<zx-y<z 的形式,将其变化为 xyz1x-y \leq z-1 的形式

为了得到正确的结果,我们必须保证至少存在一个点,通过这个点我们可以遍历所有的 。(注意不是点,下文会说明)。

边是我们在图论中的理解,回到求不等式解的问题当中。遍历不到某条边就相当于无法保证满足不等式组中的所有约束,答案就可能产生错误。

遍历不到某个点没有任何关系,说明其没有任何约束,随便取什么值都可以。

如果可以通过某个点走到任意点上,那么也可以通过该点走过任何边。(边是连接点和点的,必然可以通过所有边)

具体实现时,往往在原图上附加一个超级源点,这个顶点与每个顶点连上一条权值为 00 的边。

这里有一个有趣的结论,我们从 00ii 加了一条边,转化成不等式就相当于 xix0x_i\leq x_0xix_i 在图里又相当于从源点到 ii 的最短路大小,x0x_0 在图中又意味着源点。也就是说,当我们一开始就把 x0x_0 的解定为X时,所有未知数的解都不会大于X(dis[0]=X)

线性约束 一般是在一维空间中给出一些变量(一般定义位置),然后告诉你某两个变量的约束关系,求两个变量 aabb 差值的最大值或最小值。

区间约束 一般是给出一些区间,要求对于[ai,bi][a_i,b_i] 这个区间,区间内的数字大于/不大于/小于/不小于 cic_i 。然后问在这个约束条件下整数集合最少包含多少数。

先看看我们已知的限制条件,对于一个区间 [l,r][l,r]i=li=rci\sum_{i=l}^{i=r}\geq c_i ,这很明显不符合差分约束的不等式格式。考虑转化成前缀和去做。这就变成了 sum[r]sum[l1]cisum[r]-sum[l-1] \geq c_i

定义单位最大值为MAX。

同时,一定要记住,前缀和还有这两个性质sum[i]sum[i1]sum[i] \geq sum[i-1]sum[i]sum[i1]MAXsum[i]-sum[i-1]\leq MAX 。有了这两个性质就能保证是连通图了。**注意:转化成前缀和后0这个点必须存在。**如果不存在需要其他点需要自增。

未知条件约束 是指在不等式的右边不一定是个常数,可能是个未知数。可以通过枚举或者二分这个未知数,把未知数变成已知数,通过判断方程组是否有解来判断枚举的这个数是否可行。

floyd相关

floyd

时间复杂度为 O(n3)O(n^3)nn 表示点数

1
2
3
4
5
6
7
8
9
10
11
12
#define INF 0x3f3f3f3f
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) dis[i][j] = 0;
else dis[i][j] = INF;
//算法结束后,dis[i][j]表示i到j的最短距离
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for( int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

floyd求传递闭包

1
2
3
4
5
//mp[i][j]表示图中i和j是否连通
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1;j <= n; j++)
mp[i][j] |= mp[i][k] & mp[k][j];

最小生成树相关

朴素版prim求最小生成树

时间复杂度 O(n2+m)O(n^2+m)nn 表示点数,mm 表示边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define INF 0x3f3f3f3f
int n;//n表示点数
int mp[MAXN][MAXN];//邻接矩阵,存储所有边
int dis[MAXN];//存储其他点到最小生成树的距离
int vis[MAXN];//存储每个点是否已经在生成树中

//如果图不连通则返回INF,否则返回最小生成树的树边权重之和
int prim() {
memset(dis, 0x3f, sizeof(dis));
int res = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (t == -1 || dis[t] > dis[j]))
t = j;
if (i && dis[t] == INF) return INF;
if (i) res += dis[t];
vis[t] = 1;
for(int j = 1; j <= n; j++)
dis[j] = min(dis[j], mp[t][j]);
}
return res;
}

Kruskal求最小生成树

时间复杂度为 O(mlogm)O(mlogm)nn 表示点数,mm 表示边数

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
#define INF 0x3f3f3f3f
int n, m;//n表示点数,m表示边数
int f[MAXN];//并查集的父节点数组
struct EDGE {
int a, b, w;
bool operator< (const EDGE &W) const {
return w < W.W;
}
}edge[MAXM];

int findx(int x) {
if (x == f[x]) return x;
return f[x] = findx(f[x]);
}

int kruskal() {
sort(edge + 1, edge + 1 + m);
for (int i = 1; i <= n; i++) f[i] = i;//初始化并查集
int res = 0, cnt = 0;
for (int i = 1; i <= m; i++) {
int x = edge[i].a, y = edge[i].b, w = edge[i].w;
x = findx(x), y = findx(y);
if (x != y) {
f[y] = x;
cnt++;
res += w;
}
}
if (cnt < n - 1) return INF;
return res;
}

LCA相关

倍增求LCA

预处理时间复杂度 O(nlogn)O(nlogn) ,单次查询时间复杂度 O(logn)O(logn)

f[i][j]f[i][j] 表示从 ii 向上走 2j2^j 次步的节点的编号 0jlogn0 \leq j \leq logn

depth[i]depth[i] 表示节点 ii 的深度,默认根节点的深度为 11 。节点 ii 的深度=与根节点的距离+1。

步骤一:把两个点跳到同一层

步骤二:在两个点深度相等后,一起往上跳相同的距离

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
int n, m, rt;//点数,边数,根
int depth[MAXN];//点的深度
int fa[MAXN][25];

void build(int rt) {
//预处理fa数组
memset(depth, 0x3f, sizeof(depth));
depth[0] = 0;//哨兵
depth[rt] = 1;
queue<int> q;
q.push(rt);
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (depth[to] > depth[now] + 1){
//to还没搜索过
depth[to] = depth[now] + 1;
q.push(to);
fa[to][0] = now;//to的上一层为now
for (int k = 1; k <= 24; k++) {
fa[to][k] = fa[fa[to][k-1]][k-1];//向上更新
}
}
}
}
}

int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
for (int k = 24; k >= 0; k--) {
//跳到相同的深度
if (depth[fa[x][k]] >= depth[y])
x = fa[x][k];
}
if (x == y) return x;
for (int k = 24; k >= 0; k--) {
//一起往上跳
if (fa[x][k] != fa[y][k]) {
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0];
}

void solve() {
build(rt);
while (m--) {
int x, y;
cin >> x >> y;
cout << lca(x, y) <<endl;
}
}

Tarjan离线算法求LCA

时间复杂度 O(n+m)O(n+m)

在深度优先搜索时将所有点分为三大类:

  • 还未遍历过的点 蓝
  • 正在搜索中的分支(从根节点到当前节点的一条路径) 红
  • 已经回溯完的点 绿

红色的点和绿色的点的 LCALCA 就是并查集意义中绿色点的代表元素。通过维护并查集就可以求出两个点的 LCA 。只要在 dfsdfs 的时候维护并查集即可,维护的复杂度为 O(n)O(n)

建图部分(包括连边和记录查询方案)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 1; i < n; i++) {
//连边
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
// vector <pii> mp[MAXN] first表示另一个点的编号,second表示方案的编号
for (int i = 1; i <= m; i++) {
//记录查询方案
int u, v;
cin >> u >> v;
if (u != v) {
mp[u].push_back({v, i});
mp[v].push_back({u, i});
}
}

然后对任意点跑一个 tarjantarjan

1
tarjan(1);

tarjantarjan 算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tarjan(int now) {
vis[now] = 1; //表示正在搜索这个点
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (!vis[to])
tarjan(to), f[to] = now; //合并到根节点
}
for (auto x : mp[now]) {
//遍历和该点相关的所有查询方案
int to = x.first;
int tim = x.second;
if (vis[to] == 2) {
//该点已完成回溯,LCA为f[to]
int fa = findx(to);
ans[tim] = dis[now] + dis[to] - 2 * dis[fa];
}
}
vis[now] = 2; //该点已完成回溯
}

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
int n, m;                      //点数和边数
int head[MAXN], h[MAXN]; //如果有需要,h表示原图的表头,head表示求完强连通分量后的表头
int low[MAXN], dfn[MAXN], num; //时间戳相关定义
int vis[MAXN];
stack<int> st; //栈相关定义
int key[MAXN]; //标记每个点属于哪个强连通分量
int scc, sccc[MAXN]; //强连通分量个数和强连通分量要维护的东西
void tarjan(int x) {
low[x] = dfn[x] = ++num; //更新时间戳
st.push(x);
vis[x] = 1; //入栈
for (int i = h[x]; i; i = edge[i].next) {
int y = edge[i].to;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (vis[y] == 1) {
low[x] = min(low[x], dfn[y]);
}
}
if (low[x] == dfn[x]) {
scc++;
int now = -1;
while (now != x) {
now = st.top();
st.pop();
vis[now] = 0; //出栈标记
key[now] = scc;
sccc[scc]++; //维护强连通分量size
}
}
}

void solve() {
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
}

对于DAG图而言,通过所有入度数为 00 的点即可遍历到所有的点。

对于DAG图而言,至少需要加 max(入度数为0的点的个数, 出度数为0的点的个数) 条边,就能使得这张图成为强连通分量。

连通分量相关

强连通分量逆序求拓扑

tarjantarjan 的强连通分量的求解顺序的逆序是一个拓扑序。可以通过倒着遍历强连通分量编号的写法来代替宽搜拓扑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//以最长链方案统计为例
for (int now = scc; now; now--) {
if (!dp[now])
dp[now] = sccc[now], cnt[now] = 1;
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
int val = sccc[to];
if (dp[to] == dp[now] + val) {
cnt[to] = (cnt[to] + cnt[now]) % mod;
}
else if (dp[to] < dp[now] + val) {
dp[to] = dp[now] + val;
cnt[to] = cnt[now];
}
}
}

缩点

把环看成一个点进行后面的算法。一般缩点后的点权是环路中所有点的点权和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n;
int key[MAXN];
int h[MAXN]; //原图
int head[MAXN]; //新图
void solve() {
for (int now = 1; now <= n; now++) {
for (int i = h[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (key[now] == key[to])
continue; //如果两端属于一个强连通分量放弃连边
add_edge(head, key[now], key[to]); //将两个点对应的强连通分量编号连边
//单点也属于强连通分量
}
}
}

这是遍历点,也可以遍历边。如果一条边的两个端点不是属于两个强连通分量,就在新图上连一条边。

缩点哈希判重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<ll> s;
for (int now = 1; now <= n; now++) {
for (int i = hh[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (key[now] == key[to])
continue;
ll hash = key[now] * 1000000ll + key[to];
if (s.count(hash))
continue; //判重边
add_edge(head, key[now], key[to]);
indgr[key[to]]++;
s.insert(hash);
}
}

边双连通分量

对于一张连通的无向图,如果删除图中的某条边之后原先的图不能成为连通图,那么这条边就被称为

极大的不包含桥的连通块,被称为 边双连通分量(e-dcc)

对于边双连通分量,不管删除哪条边,图依旧是连通的。

  • 如何判断桥?

    ​ 判断 yy 能否走到 xx 的祖先节点!!!如果不能,则为桥。

    dfn(x)<low(y)dfn(x)<low(y)

  • 如何找到所有边双连通分量?

    ​ 利用栈维护,如果dfn(x)==low(x)dfn(x)==low(x) ,表示 xx 无法返回他的祖先节点,说明 xx 的父节点与 xx 的边即为桥,还在栈当中的节点即为边双连通分量。

对于一棵树,所有边都是桥。

写的时候因为是无向边,我们要新加一个参数 prepre (prepre 是边不是点)防止走回头路,因为如果走回头路的话必然找不到桥了。

要新开一个数组 bridge[MAXN]bridge[MAXN] 来记录每条边是否是桥。如果一条边是桥,那么他的反向边也是桥。

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
int n, m;                       //点数,边数
int num, dfn[MAXN], low[MAXN]; //时间戳相关
int dcc, key[MAXN], dccc[MAXN]; //边双连通分量相关
stack<int> st;
vis[MAXN]; //栈
int bridge[MAXM]; //判断某条边是不是桥,1表示是

void init() {
memset(head, 0, sizeof(head));
tot = 0;
memset(bridge, 0, sizeof(bridge));
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
num = 0;
dcc = 0;
}

int get(int x) {
//求反向边
if (x & 1)
return x + 1;
return x - 1;
}

void tarjan(int x, int pre) {
dfn[x] = low[x] = ++num;
st.push(x);
vis[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
int y = edge[i].to;
if (!dfn[y]) {
tarjan(y, i); //从i这条边走过来的
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) {
// y无法返回x的祖先
bridge[i] = bridge[get(i)] = 1;
}
}
else if (i != get(pre)) //这条路不是回头路且时间戳更新过
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
dcc++;
int now = -1;
while (now != x) {
now = st.top();
st.pop();
vis[now] = 0;
//维护边双连通分量相关信息
key[now] = dcc;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
tarjan(1, 0);
int flag = 1; //整个图是不是连通图

for (int i = 1; i <= n; i++) {
//有点未更新时间戳表示图不连通
if (!dfn[i]) {
flag = 0;
break;
}
}

for (int i = 1; i <= tot; i++)
if (bridge[i]) //对所有桥进行操作
}

结论:对于一个无向连通图,将图中所有的双连通分量缩点后,定义那些度数为 11 的点个数为 cntcnt 。则最少需要添加 (cnt+1)/2(cnt+1)/2 条边,就能使原图变为双连通分量。

桥的缩点

桥的缩点其实好写一点。边的信息要记录两端。已知缩点后的图是一棵树,所有的树边都是桥。所以在判完所有桥后,遍历每条边。若该边是桥,就在新图上把两个端点代表的 keykey 值连条边。

1
2
3
4
5
6
for (int i = 1; i <= tot; i += 2) {
if (bridge[i]) {
add_edge(h, key[edge[i].u], key[edge[i].v]);
add_edge(h, key[edge[i].v], key[edge[i].u]);
}
}

点双连通分量

如果删除图中的某个点与和他连的边之后原先的图不能成为连通图,那么这个点就被称为 割点

对于一个连通块 uu ,如果不存在另一个连通块 vv ,使得 vv 包含 uu 中所有的元素并且 vv 含有 uu 中没有的元素,称 uu极大的

每一个割点至少属于两个连通分量。

每一个点双连通分量至少包含一个割点。

依旧引入 时间戳 的概念

  • 如何求割点?

还是类似,由 xx 连向 yy ,去掉 xx 和与之相连的边后,yy 不能返回 xx 的祖先节点。但如果 xx 是整个图的根节点,那么还得继续讨论

  1. xx 不是根节点,dfn[x]low[y]dfn[x] \leq low[y]
  2. xx 是根节点,满足 xx 至少有两个子节点 y1,y2y_1,y_2 ,使得low[y1]dfn[x]ANDlow[y2]dfn[x]low[y_1]\geq dfn[x] AND low[y_2]\geq dfn[x]
  • 如何维护所有点双连通分量

还是需要一个栈。

当发现 dfn[x]low[y]dfn[x] \leq low[y] 时,说明 yy 无法返回 xx 的祖先节点,说明原图中点双连通分量的个数 vccvcc 加一。如果 xx 不是根节点或者 cnt>1cnt>1 ,说明 xx 是割点。此时就将栈中元素弹出直至弹出 yy 。并且 xx 也属于该点双连通分量。

特判一下一个孤立点的情况,因为这也算一个点双连通分量。

缩点步骤:

  1. 每个割点单独作为一个点
  2. 每个点双连通分量向它所包含的那个割点连条边

这样操作完之后,每个点双连通分量的度数就是其所连接的割点的个数。

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
int n, m;                      //点数和边数
int dfn[MAXN], num, low[MAXN]; //时间戳相关
int dcc;
vector<int> dccc[MAXN];
stack<int> st;
int iscut[MAXN]; //判断是否为割点
int root; //遍历时随机选择的根节点
int cnt_unpassed; //连通块数量个数
void tarjan(int x) {
dfn[x] = low[x] = ++num;
int cnt = 0; //删除该点,原先的一个连通块变成cnt个连通块
if (x == root && head[x] == 0) {
//特判孤立点
dcc++;
dccc[dcc].emplace_back(x);
return;
}
for (int i = head[x]; i; i = edge[i].next) {
int y = edge[i].to;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (dfn[x] <= low[y]) {
// y无法到达x的祖先
cnt++;
if (x != root || cnt > 1)
iscut[x] = 1; // x是割点
dcc++;
int now = -1;
while (now != y) {
now = st.top();
st.pop();
dccc[dcc].emplace_back(now);
}
dccc[dcc].emplace_back(x); //把x也要push进去
}
}
else
low[x] = min(low[x], dfn[y]);
}
}

void solve() {
for (root = 1; root <= n; root++) {
if (!dfn[root]) {
cnt_unpassed++; //连通块个数+1
tarjan(root);
}
}

for (int i = 1; i <= dcc; i++) {
int cnt = 0; //统计一个点双连通分量内的割点个数
for (int j = 0; j < dccc[i].size(); j++) {
if (iscut[dccc[i][j]] == 1) //如果是割点
cnt++;
}
}
}

二分图相关

染色法判断二分图

一个图的顶点可以分为两个集合 XXYY ,图的所有边一定是有一个顶点属于 XX ,另一个顶点属于集合 YY ,则称该图为 二分图

二分图当且仅当图中不含 奇数环

由于图中不含奇数环,所以染色过程中一定没有矛盾。如果能完美地将一张图的所有点染色成功,即为二分图;如果产生矛盾,则不是二分图。

时间复杂度 O(n+m)O(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
int n, m;                //点数,边数
int color[MAXN]; //表示每个点的颜色,-1表示还未染色
bool dfs(int now, int c) {
// x表示点编号,c表示颜色
color[now] = c;
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (color[to] == -1) {
if (!dfs(to, !c)) //搜完后出现了矛盾
return false;
}
else if (color[to] == c) //之前的结果和现在的结果产生矛盾
return false;
}
return true;
}

void solve() {
for (int i = 1; i <= n; i++) {
if (color[i] == -1) {
if (!dfs(i, 0)) {
//染色时出现了矛盾
cout << "No" << endl;
return;
}
}
}
cout << "Yes" << endl;
}

二分图染色的过程中只要合法,染什么颜色都是无所谓的,到最后颜色是互补的。可以利用这个性质记录下来两种颜色的个数的和。然后根据题目的具体条件将颜色人为分配为较小的或较大的。就像下面这样

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int j = 0; j <= 30; j++) {
memset(color, -1, sizeof(color));
for (int i = 1; i <= n; i++) {
if (color[i] == -1) {
if (!dfs(i, j, 0)) {
cout << -1 << endl;
return;
}
}
ans += base[j] * min(sum0, sum1);
sum0 = 0, sum1 = 0;
}
}

二分图的最大匹配

具体可以理解成男女婚配问题,给出一些男女之间的爱慕关系,求出情侣的最多数量。遍历所有其中一个集合的人,如果发现他喜欢的人都心有所属,那么一个个绿过去,看看她原来的对象能否找到一个新的女朋友。如果能找到,就绿了他;如果不能,说明这个人注孤生。

经过 NNDFSDFS ,匹配到另一个集合的尚未匹配的人就结束当前搜索,开始下一趟搜索。

最坏时间复杂度 O(nm)O(nm) 即遍历所有边,实际运行时间一般远小于 O(nm)O(nm)

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
int n, nn, m;    // n表示第一个点集中的点数,nn表示第二个点集中的点数
int vis[MAXN]; // vis表示第二个集合中的某个点是否已经被遍历过
int match[MAXN]; // match表示第二个集合中的某个点当前匹配的第一个集合中的点是哪个
int ans = 0; //最大匹配数

bool find(int now) {
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (!vis[to]) {
//如果这个now可能的对象还未搜索过
vis[to] = 1; //标记一下,防止重复搜索
if (match[to] == 0 || find(match[to])) {
//如果她当前还没对象或者可以绿她的对象
match[to] = now;
return true;
}
}
}
return false;
}

void solve() {
for (int i = 1; i <= n; i++) {
//跑N趟DFS
memset(vis, 0, sizeof(vis));
if (find(i))
ans++;
}
cout << ans << endl;
}

最小点覆盖

结论:最大匹配数=最小点覆盖

给出一张图,选出最少的点,使得每条边的两个端点至少有一个被选出来。

二分图 中,最小点覆盖=最大匹配数。

最大独立集

从一个图中选出最多的点,使得选出的点之间是没有边相连的。

二分图 中,最大独立集=点数-最大匹配

从定义下手,相当于在一个图中去掉最少的点,将所有边都破坏掉。

也就等价于,找到最少的点,使得这些点能覆盖所有的边。

DAG图的最小路径点覆盖

对于一张DAG图,选出最少的互不相交的边使得其能覆盖图中所有的点。

在二分图中,最小路径覆盖数=顶点数-最大匹配

因为无法确保DAG图是二分图,所以要拆点,就像种类并查集那样扩大原先的数组为 22 倍。

左边的点称为 出点 ,右边的点称为 入点 ,每次从左边连到右边。这样就能确保一定是二分图。

此时将原图中的路径互不相交,所以每一个点最多只有一个出度和入度,这就意味着在新图中,左部每一个点最多连出一条边,右边的点最多连入一条边,每个点最多只会属于一条边。

此时

  • 原图中的路径 对应 新图中的一组匹配
  • 原图中每一条路径的终点 对应 新图左部的非匹配点

总结:

求原图中互不相交路径数 求路径终点数最少 求左部分非匹配点最少 求最大匹配

最小路径重复点覆盖

在最小路径覆盖问题的基础上,去掉互不相交。

模板题:求一遍传递闭包后跑一下匈牙利算法求最大匹配。答案就是 nansn-ans

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
int n, nn, m;    // n表示第一个点集中的点数,nn表示第二个点集中的点数
int vis[MAXN]; // vis表示第二个集合中的某个点是否已经被遍历过
int match[MAXN]; // match表示第二个集合中的某个点当前匹配的第一个集合中的点是哪个
int ans = 0; //最大匹配数

bool find(int now) {
for (int i = head[now]; i; i = edge[i].next) {
int to = edge[i].to;
if (!vis[to]) {
//如果这个now可能的对象还未搜索过
vis[to] = 1; //标记一下,防止重复搜索
if (match[to] == 0 || find(match[to])) {
//如果她当前还没对象或者可以绿她的对象
match[to] = now;
return true;
}
}
}
return false;
}

void solve() {
for (int i = 1; i <= n; i++) {
//跑N趟DFS
memset(vis, 0, sizeof(vis));
if (find(i))
ans++;
}
cout << ans << endl;
}

欧拉路径与欧拉回路

基本概念:

欧拉路径:图中的一条路径,能够通过图中的每一条边,并且每条边仅通过一次

欧拉回路:就是闭合的欧拉路径

欧拉图:包含欧拉回路的图

判断:

无向图(连通)

  • 欧拉路径:度数为奇数的点只能有 00 个或 22 个。
  • 欧拉回路:度数为奇数的点只能有 00 个。

有向图(连通)

  • 欧拉路径:要么所有点的出度均等于入度;要么除了两个点之外,其余所有点的入度等于出度。剩余的两个点一个点满足 出度-入度=1 (起点),另一个满足 入度-出度=1 (终点)。
  • 欧拉回路:所有点的出度均等于入度

算法实现:

利用 dfsdfs 来找到一条欧拉回路。

以无向图为例,因为每个点的度都为偶数,所以我们从任意一个点出发,假设所有点的度数都为 22 ,那么 dfsdfs 一定会回到起点,从而形成一个回路。

如果度数都为 22 ,那么现在就是一条欧拉回路;假设度数不全为 22 ,有 4,6,84,6,8 …那么在 dfsdfs 过程中,当走到这些点(假设走到点 nownow )上时,可能会走到其他环上,但是由于度数是偶数,所以如果走到其他环上,最后也会回到点 nownow

dfsdfs过后,一定会形成许多环,环与环之间有一个交点,在回溯过程中将这些点添加到答案中,就是一条欧拉回路。
有向图同理。

概括:分三步,删边,爆搜,记录答案(路径)

有向图和无向图的欧拉回路

模板题:给出一张图,给出它是有向或无向,求一条欧拉回路

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
int type;                     //有向图 or 无向图
int n, m; //点,边的数量
int ans[MAXM], cnt; //记录欧拉回路用,必须是边的数量
int vis[MAXM]; //标记某条边有没有走过
int indgr[MAXN], oudgr[MAXN]; //点的入度和出度来表示度数

void dfs(int now) {
//判重删边,dfs,记录答案
for (int &i = head[now]; i;) {
//改变引用后就能直接删边了
if (vis[i]) {
//这条边用过了
i = edge[i].next; //删除这条边
continue;
}
vis[i] = 1;
if (type == 1) //如果是无向边,反向边也要标记删除
vis[get(i)] = 1;
int id; //表示边的编号
if (type == 1) {
//无向图
id = (i + 1) / 2;
if (i % 2 == 0) //本题特有的脑瘫条件,不用管
id = -id;
}
else //有向图
id = i;
int j = edge[i].to;
i = edge[i].next;
dfs(j);
ans[++cnt] = id;
}
if (type == 2) {
//判断度数合法性
for (int i = 1; i <= n; i++) {
if (indgr[i] != oudgr[i]) {
cout << "NO" << endl;
return;
}
}
}
else {
for (int i = 1; i <= n; i++) {
if ((indgr[i] + oudgr[i]) & 1) {
cout << "NO" << endl;
return;
}
}
}

for (int i = 1; i <= n; i++) {
//找一个非孤立点去遍历整张图
if (head[i] != 0) {
dfs(i);
break; //一定要break掉,因为有非连通的情况存在
}
}
if (cnt < m) {
//判断图的连通性
cout << "NO" << endl;
}
cout << "YES" << endl;
for (int i = cnt; i > 0; i--) //欧拉路要倒着输出
cout << ans[i] << " ";
cout << endl;
}

无向图欧拉路径

模板题,输出答案序列字典序最小的欧拉路径(为点)

一个个分析:

  • 字典序最小。记录欧拉路径时是类似于栈一样后进先出,最后再逆序输出。所以只要保证小的点尽可能的放到序列后面即可。即从小到大遍历。
  • 欧拉路径。找到第一个度为奇数的点对他爆搜。特判欧拉回路的情况,因为此时没有度为奇数的点。
  • 答案用点标记。更新的时候更新点的编号,为了方便可以用邻接表,还能顺便实现从小到大搜的要求。
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 505
#define MAXM 2105
int mp[MAXN][MAXN];
int d[MAXN]; //存储度数
int n, m;
int ans[MAXM], cnt;

void dfs(int now) {
for (int i = 1; i <= 500; i++) {
if (mp[now][i]) {
mp[now][i]--, mp[i][now]--; //删边
dfs(i); //爆搜
}
}
ans[++cnt] = now; //记录答案
}

void solve() {
cin >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
mp[u][v]++, mp[v][u]++;
d[u]++, d[v]++;
}
int start = 0;
while (!d[start])
start++; //特判欧拉回路的情况
for (int i = 1; i <= 500; i++) {
if (d[i] & 1) {
//如果是一条欧拉回路前面必须做过处理,否则出不来
start = i;
break;
}
}
dfs(start);
for (int i = cnt; i; i--) //欧拉路要倒着输出
cout << ans[i] << endl;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
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
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int f[MAXN];
int din[MAXN], dout[MAXN];
int st[MAXN];
int n;
int find(int x) {
if (x == f[x])
return x;
else
return f[x] = find(f[x]);
}
int g[50][50];

void solve() {
int n;
cin >> n;
memset(st, 0, sizeof st);
memset(din, 0, sizeof din);
memset(dout, 0, sizeof dout);
for (int i = 0; i <= n; i++) {
f[i] = i;
}
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int a = s[0] - 'a', b = s[(int)s.size() - 1] - 'a';
st[a] = st[b] = 1;
g[a][b]++;
dout[a]++, din[b]++;
int pa = find(a), pb = find(b);
f[pa] = pb;
}
int tmp = -1;
int res = 0;
for (int i = 0; i < 26; i++) {
//图的连通性
if (st[i]) {
if (tmp == -1)
tmp = find(i);
else {
if (tmp != find(i)) {
res = 1;
break;
}
}
}
}
int start = 0, ed = 0;
for (int i = 0; i < 26; i++) {
//判断有向图入度出度的合法性
if (din[i] != dout[i]) {
if (dout[i] == din[i] + 1)
start++;
else if (din[i] - 1 == dout[i])
ed++;
else {
res = 1;
break;
}
}
}
if (start != 0 || ed != 0) {
if (start != 1 || ed != 1)
res = 1;
}
if (res == 1) {
cout << "The door cannot be opened." << endl;
}
else {
cout << "Ordering is possible." << endl;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
}

如果要求具体的欧拉路径,判断完连通性和度数合法性后,对最小编号的点进行一遍 dfsdfs 即可,模板套用上两个邻接矩阵或邻接表的模板。