发表更新学习总结 / 图论24 分钟读完 (大约3568个字)

二分图与图的连通

update: 2023/12/12 fixed pictures

学习内容

本周学习内容：

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
Week 1
|- 二分图
|  |- 二分图的判定
|  |  |- 染色法
|  |  |- 不存在奇环（长为奇数的环）
|  |- 二分图最大匹配（匈牙利算法）
|  |- 二分图最小点覆盖（König定理二分：二分图中，最小点覆盖=最大匹配）
|  |- 二分图最大独立集（二分图中，最大独立集=n-最小点覆盖）
|  |- 例题（关于建边）
|- 图的联通
|  |- 定义（只有概念，详细定义见下）
|  |  |- 无向图中的定义
|  |  |  |- 连通图
|  |  |  |- 子图
|  |  |  |- 连通子图
|  |  |  |- 连通分量（最大联通子图）
|  |  |- 有向图中的定义
|  |  |  |- 强连通图
|  |  |  |- 强连通子图
|  |  |  |- 强连通分量
|  |  |  |- k连通图（双连通图）
|  |  |  |- 割点
|  |  |  |- 桥
|  |  |  |- 双连通分量
|  |  |  |- 点双连通分量
|  |  |  |- 边双连通分量
|  |- 算法
|  |  |- 如何求强连通分量（SCC）= 如何缩点
|  |  |  |- Kosaraju算法
|  |  |  |- Tarjan算法
|  |  |  |- Gabow算法（略）
|  |  |- 如何求桥/割点
|  |  |  |- Tarjan算法（对还是它）
|  |  |- 如何求点/边双连通分量
|  |  |  |- Tarjan算法（啊？）

学习内容的模板（以及图论常用模板）

二分图最大匹配（König算法）

例题

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
vector<int> g[MAXN];
bool vis[MAXM];
int lst[MAXM];

bool konig(int u) {
	for (auto &v : g[u]) {  // auto好用的
		if (vis[v]) continue;
		vis[v] = 1;
		if (lst[v] == 0 || findargu(lst[v])) {
			lst[v] = u;
			return 1;
		}
	}
	return 0;
}

int main() {
    int cnt = 0;
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof vis);  // 打时间戳可以优化常数
		if (findargu(i)) cnt++;
	}
	cout << cnt;
}

强连通分量（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
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;  // 两个关键数组：dfn, low
bool ins[MAXN];
int st[MAXN], top;  // 手写栈
int tag[MAXN], tagcnt;  // 标记数组，tagcnt是强连通分量的个数

void tarjan(int u) {
	dfn[u] = low[u] = ++dfncnt;
	ins[u] = 1;
	st[++top] = u;
	for (auto &v : g[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]) {
		tagcnt++;
		while (1) {
			int v = st[top--];
			ins[v] = 0;
			tag[v] = tagcnt;
			if (v == u) break;
		}
	}
}

int main() {
    // 因为不确定图是否连通，所以对于每一个点都要跑一遍Tarjan
    for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}

    // 缩点(建新图)
    vector<int> h[MAXN];
    for (int i = 1; i <= m; i++) {
        if (tag[e[i].u] != tag[e[i].v]) {
            h[tag[e[i].u]].push_back(tag[e[i].v]);
        }
    }
}

割点

例题

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
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;  // 求割点不需要使用栈

// 割点
bool cut[MAXN];  // 标记那些点是割点
int cnt;  // 统计割点个数
void tarjan(int u, int f) {
	dfn[u] = low[u] = ++dfncnt;
	int sons = 0;
	for (auto &v : g[u]) {
		if (!dfn[v]) {
			tarjan(v, u);
			sons++;
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u] && !cut[u] && u != rt) {  // 割点的判断-1
				cut[u] = 1;
				cnt++;
			}
		} else if (dfn[v] < dfn[u] && v != f) low[u] = min(low[u], dfn[v]);
	}
	if (u == rt && sons >= 2 && !cut[u]) {  // 割点的判断-2
		cut[u] = 1;
		cnt++;
	}
}

桥

例题（没有例题，不要点开）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;  // 求桥还是不需要使用栈

// 桥（输出到stdout）
void tarjan(int u, int f) {
	dfn[u] = low[u] = ++dfncnt;
	int sons = 0;
	for (auto &v : g[u]) {
		if (!dfn[v]) {
			tarjan(v, u);
			sons++;
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) {  // 桥的判断
				cout << u << " " << v << endl;
			}
		} else if (dfn[v] < dfn[u] && v != f) low[u] = min(low[u], dfn[v]);
	}
}

点双连通分量

例题

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
int dfn[MAXN], low[MAXN], dfncnt;
int tag[MAXN], tagcnt;
stack<int> st;
int rt;
vector<int> ans[MAXN];
int cnt;

void tarjan(int u) {
	dfn[u] = low[u] = ++dfncnt;
	st.push(u);
	if (u == rt && !head[u]) {  // 判断孤立点
		ans[++cnt].push_back(u);
		return ;
	}
	for (int i = head[u]; i; i = g[i].nxt) {  // 这里使用链式前向星
		int v = g[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				cnt++;
				int p;
				do {
					p = st.top();
					st.pop();
					ans[cnt].push_back(p);
				} while (v != p);
				ans[cnt].push_back(u);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

dijkstra算法

例题0 例题1 例题2 （例题0是板子，例题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
// 值得注意的一点是，dijkstra算法处理最长路时会损失效率（虽然可以卡过），所以在处理最长路时使用SPFA会更加有效（尽管它死了）
// 上述内容对应例题2，如果使用dijkstra算法的话会WA#3
struct node{
	int dis, u;
	bool operator < (const node& a) const {
		return dis > a.dis;
	}
};

bool vis[MAXN];
int dis[MAXN];
priority_queue<node> q;

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto &i : h[u]) {
			int v = i.first, w = i.second;
			if (dis[v] > dis[u]+w) {
				dis[v] = dis[u]+w;
				q.push({dis[v], v});
			}
		}
	}
}

SPFA算法

例题0 例题1 （例题0是板子，例题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
// SPFA尽管死了并且它的效率要比dijkstra慢，但是其拥有良好的负环检测系统，关键是：最长路能用
vector<int> h[500010];
int dis[500010], cnt[500010];
bool vis[500010];
queue<int> q;

// 这是最长路并且统计的是点权，改为最短路/统计边权只要参考dijhstra就好
bool spfa() {
	memset(dis, -1, sizeof dis);  // 最短路需改
	int f = tag[s];
	q.push(f);
	dis[f] = mon[f];
	vis[f] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (auto &i : h[u]) {
			if (dis[i] < dis[u]+mon[i]) {  // 最短路/统计边权需改
				dis[i] = dis[u]+mon[i];  // 最短路/统计边权需改
				cnt[i] = cnt[u]+1;
				if (cnt[i] >= tagcnt) return 0;
				if (!vis[i]) {
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}
	return 1;
}

学习内容——各种定义

强连通/连通图

在无向图中，任意两点都直接或间接连通，则称该图为 连通图(connected).

相应的，有向图中任意一点都存在路径到达任意另一点，则称该有向图为 强连通图(strong connected) .

子图

在一个图 $H$ 中，$H$ 的所有边属于图 $G$ 的所有边，$H$ 的所有点属于图 $G$ 的所有点，则称图 $H$ 是图 $G$ 的 子图(subgraph) .

连通分量

无向图 $G$ 的最大连通子图称为 $G$ 的 连通分量(connected components) .

何为最大连通子图？这个子图是 $G$ 的连通子图，将 $G$ 的任何一个不在这张子图中的点加入这张子图后，该子图不再连通.

强连通分量（SCC）

在任意有向图中能够实现强连通的部分我们称其为 **强连通分量(Strongly connected component)**，如下图，蓝色框内的分别是一个强连通分量.

https://www.z4a.net/images/2023/12/12/wikiimg.png

如果把每个强连通分量收缩为单个顶点，得到的是一个 **有向无环图(DAG)**，于是我们可以在这个图的基础上进行拓扑排序，详见此例题.

而求这个强连通分量，我们可以使用两个算法：Kosaraju算法，Tarjan算法.

Kosaraju算法的流程如下：

  1. 重复寻找图 $G$ 中未被讨论的点，从它开始DFS后序遍历图 $G$ ，遍历到的点置为已讨论，用数组记录每个点到达的先后次序，直到找不到没有讨论的点.
  2. 将图 $G$ 反向得到图 $G’$ ，重置所有点为未讨论.
  3. 一直从数组中未讨论的最后一个点出发，DFS后续遍历图 $G’$ ，DFS每完成一次，就说明找到了一个强连通分量，直到数组中没有未讨论的点.

这是Kosaraju算法的模板（之所以Kosaraju算法没有放在SCC的模板内，是因为这个算法相对于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
bool g[1001][1001];  // 这里使用的是邻接矩阵
bool vis[1001];
int lis[1001], cnt = 0;
int tag[1001], scc = 0;
bool ind[1001];

void dfs1(int u) {
	vis[u] = 1;
	for (int i = 1; i <= n; i++) {
		if (g[u][i] && !vis[i]) dfs1(i);
	}
	lis[++cnt] = u;
}

void dfs2(int u) {
	vis[u] = 1;
	tag[u] = scc;
	for (int i = 1; i <= n; i++) {
		if (g[i][u] && !vis[i]) dfs2(i);  // 这里注意，判断的边是g[i][u]，因为我们要在反图上跑dfs2()
	}
}

int main() {
	for (int i = 1; i <= n; i++) vis[i] = 0;  // 这里可以用memset
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) dfs1(i);
	}
	for (int i = 1; i <= n; i++) vis[i] = 0;
	for (int i = cnt; i >= 1; i--) {
		if (!vis[lis[i]]) {
			scc++;
			dfs2(lis[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if ((tag[i] != tag[j]) && g[i][j]) {
                // 此处为缩点
            }
		}
	}
}

接下来我们来说说Tarjan算法，这个算法相对于上个算法理解起来要困难些.

在Tarjan算法中，最为重要的两个数组是 dfn[] 和 low[] ， dfn[i] 记录的是编号为i的节点在DFS的整个过程的顺序，它会在第一次访问到 $i$ 节点时更改，此后将不会变化；low[i] 表示的是 i 与其之后遍历到的节点所能到达的节点中 dfn 最小的 dfn ，在初始化时 dfn[i]=low[i] .

Tarjan算法在运行时会生成一棵搜索树，但是我们知道，图!=树，因为图中有一些边会使得“树”有环，自然，在生成树后，有一些边会直接指向已遍历的节点，没遍历的节点会在下一步当作自己的孩子进行遍历，而指向已遍历节点的边就是导致“树”有环的罪魁祸首.按照定义，当发现有这种边的存在时，需要更新当前节点的 low[] 值，需要更新为 min(dfn[这些边指向的节点]) .而理所当然地，我们也要被孩子节点更新 low 值为 min(low[孩子节点]) .

现在我们聚焦某一个点 $i$，观察 dfn[i] 与 low[i] 的关系，以下是两种情况：

  1. dfn[i]>low[i] ，这说明 $i$ 或其子孙节点存在边连到 $i$ 上方的节点.
  2. dfn[i]=low[i] ，这说明 $i$ 以及其子孙节点无法连到 $i$ 上方的节点，那么这个点 $i$ 就是一个强连通分量在这颗搜索树的根.

但是，$i$ 的子孙节点有可能会组成另一个强连通分量，这意味着 $i$ 的子树的节点不一定和 $i$ 处在同一个强连通分量内，我们需要 栈 来解决这个问题.

现在，我们用一张图看一下 dfn[] 与 low[] 的关系。

https://www.z4a.net/images/2023/12/12/13c47f67d62e6e7e8.png

在这张图中，有 (3,4,5,6) ，7 ，8 ，1 ，2 这四个强连通块.

下图是Tarjan算法的运行过程.

https://www.z4a.net/images/2023/12/12/Tarjans_Algorithm_Animation.gif

因为SCC模板就是Tarjan算法，所以在这里不放代码.

二分图的最大匹配

何为二分图？二分图是一种特殊的无向图，它的顶点可以被分为两个互斥的独立集 $U$ 和 $V$ 的图，使得所有边都是连结一个 $U$ 中的点和一个 $V$ 中的点（如下图所示）.

https://www.z4a.net/images/2023/12/12/Biclique_K_3_5_bicolor.svg.png

何为匹配？一个图的匹配是这个图中一些边所形成的集合，满足任意集合中的两条边都没有公共顶点.

解决这个问题的算法之一是匈牙利算法.在了解这个算法之前，我们先要了解一下何为增广路（增广轨/交错轨）.

增广路：若 $P$ 是图 $G$ 中一条连通两个未匹配顶点的路径，并且已匹配和未匹配的边（也就是属匹配边集 $M$ 的边和不属 $M$ 的边）在 $P$ 上交替出现，则称 $P$ 为相对于 $M$ 的一条增广路径.

不难发现，如果我们把 $P$ 中原来属于 $M$ 边从 $M$ 中删除，把 $P$ 中原来不属于 $M$ 边加入到 $M$ 中，变化后得到的新的匹配 $M’$ 恰好比原匹配多一条边.

而匈牙利算法就是不断寻找增广路 $P$ ，通过取反操作得到更大的匹配 $M’$ 来代替 $M$ .

代码如模板所示.

割点

是无向连通图中一个顶点 $v$ , 如果删除它以及它关联的边后，得到的新图至少包含两个连通分量.

这里同样使用Tarjan算法.

思路和求SCC的Tarjan算法类似，这里直接给出结论：

一个顶点 $u$ 是割点，当且仅当满足条件 $1$ 或 $2$.

  1. $u$ 为树根，且 $u$ 有两棵及以上的子树（这很好理解吧）.
  2. $u$ 不为树根，且满足存在一条 $(u,v)$ 为树枝边使得 dfn[u] <= low[v] ，即 $u$ 有一个孩子无法到达 $u$ 以上的点.

代码如模板所示.

桥

是无向连通图中的一条边，如果删除它，得到的新图包含两个连通分量.

求桥和求割点差不多，可以直接从代码看出差别，而且判断条件的理解也和求割点差不多，此处不过多赘述.

双连通图

不含割点的无向连通图.

双连通分量

无向连通图的最大双连通子图.

点双连通分量

通过找割点获得的双连通分量（层层递进.jpg

边双连通分量 （模板没打）

通过找桥获得的双连通分量.

心得体会

主要是图论之前有接触过，所以理解概念会比较快，同时在这一周我把之前一直没弄懂的Tarjan算法搞懂了.

现在的问题主要是建边的技巧以及破题的能力，像这种题（[SDOI2010]所驼门王的宝藏），这些建边的技巧想不到.

图论的常识有些遗忘了，例如Dijkstra跑最长路不能保证时间复杂度这类东西.

关注我

链接

最新文章

归档

标签

乘法逆元1
二分图1
优化2
动态规划4
图论2
存储2
思想1
总结13
技巧1
排列组合1
数学2
数据结构1
最短路2
欧拉反演1
游记1
算法1
背包问题1
解题报告1
连通块1
随笔1
题解4
×