参考《算法竞赛进阶指南》、AcWing题库

树与图最常见的存储方式就是使用一个邻接表保存它们的边集。除非特殊声明, 默认给定 NN 个点的树或图时, 其节点编号均为 1∼N1 \sim N, 无向图中的边看作成对出现的双向边, 树看作一张具有 N−1N-1 条边的无向图, 它们的边都存 储在一个邻接表中, 邻接表以 head 数组为表头, 使用 ver 和 edge 数组分别存储边的终点和权值, 使用 next 数组模拟链表指针 (就像我们在链表与邻接表中讲解邻接表时所给出的代码那样)。

树与图的深度优先遍历, 树的 DFS 序、深度和重心

深度优先遍历

深度优先遍历, 就是在每个点 xx 上面对多条分支时, 任意选一条边走下去, 执行递归, 直至回溯到点 xx 后, 再考虑走向其他的边, 如下图所示。

根据上面提到的存储方式，我们可以采用下面的代码，调用 dfs(1)\mathrm{dfs}(1), 对一 张图进行深度优先遍历。

1
2
3
4
5
6
7
8
9
// 深度优先遍历框架
void dfs(int x) {
	v[x] = 1; //记录点x被访问过，v是visit的缩写
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		dfs(y);
	}
}

这段代码访问每个点和每条边恰好 1 次 (如果是无向边, 正反向各访问 1 次), 其时间复杂度为 O(N+M)\mathrm{O}(N+M), 其中 MM 为边数。以这段代码为框架, 我们可以统计许多关于树和图的基本信息。

时间戳

按照上述深度优先遍历的过程, 以每个节点第一次被访问 (v[x](v[x] 被珷值为 1 时) 的顺序, 依次给予这 NN 个节点 1∼N1 \sim N 的整数标记, 该标记就被称为时间翟, 记为 dfnd f n 。 例如, 在上图中, dfn[1]=1,dfn[2]=2,dfn[8]=3,dfn[5]=4,d f n[1]=1, d f n[2]=2, d f n[8]=3, d f n[5]=4,dfn[7]=5,dfn[4]=6,dfn[3]=7,dfn[9]=8,dfn[6]=9d f n[7]= 5, d f n[4]=6, d f n[3]=7, d f n[9]=8, d f n[6]=9 。

树的 DFS序

一般来讲，我们在对树进行深度优先搜索时，对于每个节点，在刚进入递归后以及即将回溯前各记录一次该点的编号，最后产生的长度为 2N2 N 的节点序列就称为树的 DFS序。

1
2
3
4
5
6
7
8
9
10
11
// DFS序
void dfs(int x) {
	a[++m] = x; //a 数组存储DFS序
	v[x] = 1; //记录点 x 被访问过
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		dfs(y);
	}
	a[++m] = x;
}

DFS 序的特点是: 每个节点 xx 的编号在序列中恰好出现两次。设这两次出现的位置为 L[x]L[x] 与 R[x]R[x], 那么闭区间 [L[x],R[x]][L[x], R[x]] 就是以 xx 为根的子树的 DFS 序。这使我们在很多与树相关的问题中, 可以通过 DFS 序把子树统计转化为序列上的区间统计。

另外, 二叉树的先序、中序与后序遍历序列, 也是通过深度优先遍历产生的。应该学握这几种遍历, 以及它们之间的联系和转化。

树的深度

树中各个节点的深度是一种自顶向下的统计信息。起初, 我们已知根节点的深度为 0 。若节点 xx 的深度为 d[x]d[x], 则它的子节点 yy 的深度就是 d[y]=d[x]+1d[y]=d[x]+1 。在深度优先遍历的过程中结合自顶向下的递推, 就可以求出每个节点的深度 dd 。

1
2
3
4
5
6
7
8
9
10
// 求树中各点的深度
void dfs(int x) {
	v[x] = 1;
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue; // 点y已经被访问过了
		d[y] = d[x] + 1; //从父节点 x 到子节点 y 递推，计算深度
		dfs(y);
	}
}

树的重心

当然, 也有许多信息是自底向上进行统计的, 比如以每个节点 xx 为根的子树大小 size⁡[x]\operatorname{size}[x] 。对于叶子节点, 我们已知 “以它为根的子树” 大小为 1 。若节点 xx 有 kk 个子节点 y1∼yky_{1} \sim y_{k} , 并且以 y1∼yky_{1} \sim y_{k} 为根的子树大小分别是 size⁡[y1],size⁡[y2],⋯ ,size⁡[yk]\operatorname{size}\left[y_{1}\right], \operatorname{size}\left[y_{2}\right], \cdots, \operatorname{size}\left[y_{k}\right], 则以 xx 为根的子树的大小就是 size⁡[x]=size⁡[y1]+size⁡[y2]+⋯+size⁡[yk]+1\operatorname{size}[x]=\operatorname{size}\left[y_{1}\right]+\operatorname{size}\left[y_{2}\right]+\cdots+\operatorname{size}\left[y_{k}\right]+1 。

对于一个节点 xx, 如果我们把它从树中删除, 那么原来的一棵树可能会分成若干个不相连的部分, 其中每一部分都是一棵子树。设 max⁡_part⁡(x)\max\_\operatorname{part}(x) 表示在删除节点 xx 后产生的子树中, 最大的一棵的大小。使 max_part 函数取到最小值的节点 pp 就称为整棵树的重心。例如上图中的树的重心应该是节点 1 。通过下面的代码, 我们可以统计出 size 数组, 并求出树的重心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 求树的重心
void dfs(int x) {
	v[x] = 1; size[x] = 1; // 子树x的大小
	int max_part = 0; // 删掉x后分成的最大子树的大小
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue; // 点y已经被访问过了
		dfs(y);
		size[x] += size[y]; // 从子节点向父节点递推
		max_part = max(max_part, size[y]);
	}
	max_part = max(max_part, n - size[x]); // n 为整棵树的节点数目
	if (max_part < ans) {
		ans = max_part; // 全局变量 ans 记录重心对应的 max_part 值
		pos = x; // 全局变量 pos 记录了重心
	}
}

图的连通块划分

下面的代码每从 xx 开始一次遍历, 就会访问 xx 能㡅到达的所有的点与边。因此, 通过多次深度优先遍历, 可以划分出一张无向图中的各个连通块。同理, 对一个森林进行深度优先遍历, 可以划分出森林中的每棵树。如下面的代码所示, cnt\mathrm{cnt} 就是无向图包含的连通块的个数, vv 数组标记了每个点属于哪一个连通块。

连通块: 若在无向图的一个子图中, 任意两个节点之间都存在一条路径 (可以互相到达), 并且这个子图是 “极大” 的 (不能再扩张), 则称该子图为无向图的一个连通块。一张不连通的无向图由 2 个或 2 个以上连通块组成, 而一张无向连通图整体是一个连通块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 划分图的连通块
void dfs(int x) {
	v[x] = cnt; // 属于第 cnt 个连通块 
	for (int i = head[x]; i; i = next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		dfs(y);
	}
}

for (int i = 1; i <= n; i++)
	if (!v[i]) {
		cnt++;
		dfs(i);
	}

树与图的广度优先遍历, 拓扑排序

广度优先遍历

树与图的广度优先遍历需要使用一个队列来实现。起初, 队列中仅包含一个起点 (例如 1 号节点)。在广度优先遍历的过程中, 我们不断从队头取出一个节点 xx, 对于 xx 面对的多条分支，把沿着每条分支到达的下一个节点 (如果尚未访问过) 插入队尾。重复执行上述过程直到队列为空。

我们可以采用下面的代码对一张图进行广度优先遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 广度优先遍历框架
void bfs() {
	memset(d, 0, sizeof(d));
	queue<int> q;
	q.push(1); d[1] = 1;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
			q.push(y);
		}
	}
}

在上面的代码中, 我们在广度优先遍历的过程中顺便求出了一个 dd 数组。对于一棵树来讲, d[x]d[x] 就是点 xx 在树中的深度。对于一张图来讲, d[x]d[x] 被称为点 xx 的层次 (从起点 1 走到点 xx 需要经过的最少点数)。从代码和示意图中我们可以发现, 广度优先遍历是一种按照层次顺序进行访问的方法, 它具有如下两个重要性质;

  1. 在访问完所有的第 ii 层节点后, 才会开始访问第 i+1i+1 层节点。
  2. 任意时刻, 队列中至多有两个层次的节点。若其中一部分节点属于第 ii 层, 则另一部分节点属于第 i+1i+1 层, 并且所有第 ii 层节点排在第 i+1i+1 层节点之前。也就是说, 广度优先遍历队列中的元素关于层次满足 “两段性” 和 “单调性”。

这两条性质是所有广度优先思想的基础, 务必牢记, 我们在 “广搜变形” 中会再次提及并探讨。与深度优先遍历一样, 上面这段代码的时间复杂度也是 O(N+M)。O(N+M) 。

拓扑排序

BFS 入度拓扑排序写法

给定一张有向无环图, 若一个由图中所有点构成的序列 AA 满足: 对于图中的每条边 (x,y),x(x, y), x 在 AA 中都出现在 yy 之前, 则称 AA 是该有向无环图顶点的一个拓扑序。 求解序列 AA 的过程就称为拓扑排序。

有向无环图: 在有向图中, 从一个节点出发, 最终回到它自身的路径被称为 “环”。不存在环的有向 图即为有向无环图。

拓扑排序过程的思想非常简单, 我们只需要不断选择图中入度为 0 的节点 xx, 然后把 xx 连向的点的入度减 1 。

入度: 在有向图中, 以节点 xx 为终点的有向边的条数被称为 xx 的入度, 以节点 xx 为起点的有向边的条数被称为 xx 的出度。在无向图中, 以 xx 为端点的无向边的条数被称为 xx 的度。

我们可以结合广度优先遍历的框架来高效地实现这个过程:

  1. 建立空的拓扑序列 AA 。
  2. 预处理出所有点的入度 deg⁡[i]\operatorname{deg}[i], 起初把所有入度为 0 的点入队。
  3. 取出队头节点 xx, 把 xx 加入拓扑序列 AA 的末尾。
  4. 对于从 xx 出发的每条边 (x,y)(x, y), 把 deg⁡[y]\operatorname{deg}[y] 减 1 。若被减为 0 , 则把 yy 入队。
  5. 重复第 3∼43 \sim 4 步直到队列为空, 此时 AA 即为所求。

拓扑排序可以判定有向图中是否存在环。我们可以对任意有向图执行上述过程, 在完成后检查 AA 序列的长度。若 AA 序列的长度小于图中点的数量, 则说明某些节点未被遍历, 进而说明图中存在环。读者可以参考下面的程序, 画图模拟拓扑排序算法。

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
// 拓扑排序, 链式前向星存图写法
void add(int x, int y) { // 在邻接表中添加一条有向边
	ver[++tot] = y, next[tot] = head[x], head[x] = tot;
	deg[y]++;
}
void topsort() {
	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (deg[i] == 0) q.push(i);
	while (q.size()) {
		int x = q.front(); q.pop();
		a[++cnt] = x; //出队时存储
		for (int i = head[x]; i; i = next[i]) {
			int y = ver[i];
			if (--deg[y] == 0) q.push(y);
		}
	}
}
int main() {
	cin >> n >> m; // 点数、边数
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	topsort();
	if (cnt != n) cout << "不存在拓扑排序";
	else {
		for (int i = 1; i <= cnt; i++)
			printf("%d ", a[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
// vector 邻接表存图
bool topoSort_bfs() {
  for (int i = 1; i <= n; ++i) // 枚举所有点
    if (indeg[i] == 0) q.push(i); // 如果入度为0，加入队列
  
  vector<int> ans;

  while (q.size()) {
    auto u = q.front(); q.pop(); // 取出队头
    
    ans.push_back(u); // 将队头节点加入答案

    for (auto v : g[u]) { // 遍历节点 u 的所有邻接点 v 
      if (--indeg[v] == 0) { // 砍掉 u -> v 这条边，v 的入度-1，如果砍掉后=0，则入队
        q.push(v);
      }
    }
  }

  if (ans.size() == n) { 
    for (int i = 0; i < ans.size(); ++i) { // 输出拓扑排序点
      cout << ans[i] << " ";
    }
    return true;
  } else { //若答案序列的长度小于图中点的数量, 则说明某些节点未被遍历, 进而说明图中存在环
    cout << "不能拓扑排序";
    return false;
  }
}

DFS 拓扑排序写法


在深度优先遍历的任意时刻, 树中节点分为三类:

  1. 已经访问完毕并且回溯的节点。在这些节点上标记一个整数 2。
  2. 已经开始递归, 但尚未回溯的节点。这些节点就是当前正在访问的节点 xx 以及 xx 的祖先。在这些节点上标记一个整数 1 。
  3. 尚未访问的节点。这些节点没有标记，保持初始值为 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
int vis[N];  
int stk[N],tt;  
//单趟dfs拓扑排序  
bool topodfs(int u) {  
	vis[u] = 1;//正在遍历中  
	for(int i = h[u]; ~i; i = ne[i]) {  
		int j = e[i]; // j 是点 u 的一个邻接点
		if(vis[j] == 0){ //j 没有遍历过  
			 if (topodfs(j) == false) return false;  
		} else if (vis[j] == 1) return false; //j正在遍历中
	    // 访问到一个正在遍历未遍历完成的点，即存在后向边，即存在环无法完成拓扑排序
	}  
	vis[u] = 2;//已经遍历完  
	stk[++tt] = u;//入栈存储  
	return true;  
}  
  
//判断整个图能否拓扑排序  
bool topoSort() {  
	for(int i = 1; i <= n; ++i){  
		if (vis[i] == 0) {  
			 if (topodfs(i) == false) return false;  
		}  
	}    
	return true;  
}

164. 可达性统计（拓扑排序）

题目描述

给定一张 NN 个点 MM 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数 N,MN,M，接下来 MM 行每行两个整数 x,yx,y，表示从 xx 到 yy 的一条有向边。

输出格式

输出共 NN 行，表示每个点能够到达的点的数量。

数据范围

1≤N,M≤300001 \le N,M \le 30000

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

输出样例：

1
2
3
4
5
6
7
8
9
10
1
6
3
3
2
1
1
1
1
1

算法分析

设从点 xx 出发能够到达的点构成的集合是 f(x)f(x), 则显然有:

f(x)={x}∪(⋃存在有向边 (x,y)f(y))f(x)=\{x\} \cup\left(\bigcup_{\text {存在有向边 }(x, y)} f(y)\right)

也就是说, 从 xx 出发能够到达的点, 是从 “ xx 的各个后继节点 yy "出发能够到达 的点的并集, 再加上点 xx 自身。所以, 在计算出一个点的所有后继节点的 ff 值之后, 就可以计算出该点的 ff 值。这启发我们先用拓扑排序算法求出一个拓扑序, 然后按照 拓扑序的倒序进行计算一一因为在拓扑序中, 对任意的一条边 (x,y),x(x, y), x 都排在 yy 之 前。

回想起状态压缩方法, 我们可以使用一个 NN 位二进制数存储每个 f(x)f(x), 其中第 ii 位是 1 表示 xx 能到 ii , 0 表示不能到 ii 。这样一来, 对若干个集合求并, 就相当于对若干个 NN 位二进制数做 “按位或” 运算。最后, 每个 f(x)f(x) 中 1 的个数就是从 xx 出发能够到达的节点数量。

这个 NN 位二进制数可以压缩成 N/32+1N / 32+1 个无符号 32 位整数 unsigned int 进行存储, 更简便的方法是直接使用 C++ STL 中为我们提供的 bitset , bitset 支持我们上述所需的所有运算。该拓扑排序 + 状态压缩算法花费的时间规模约为N(N+M)/32N(N+M) / 32 , 所需空间大小约为 N2/8N^{2} / 8 字节。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<queue>
using namespace std;
int n, m, deg[30010], a[30010];
int ver[30010], Next[30010], head[30010], tot, cnt;
bitset<30010> f[30010];

void add(int x, int y) { // 在邻接表中添加一条有向边
	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
	deg[y]++;
}

void topsort() { // 拓扑排序
	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (deg[i] == 0) q.push(i);
	while (q.size()) {
		int x = q.front(); q.pop();
		a[++cnt] = x;
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i];
			if (--deg[y] == 0) q.push(y);
		}
	}
}

void calc() {
	for (int i = cnt; i; i--) {
		int x = a[i];
		f[x][x] = 1;
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i];
			f[x] |= f[y];
		}
	}
}

int main() {
	cin >> n >> m; // 点数、边数
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	topsort();
	calc();
	for (int i = 1; i <= n; i++) printf("%d\n", f[i].count());
}
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
#include <queue>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30006;
int num[N], ans[N];
vector<int> e[N], a;
bitset<N> b[N];
queue<int> q;

int main() {
	memset(num, 0, sizeof(num));
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		num[y]++;
		b[x][y] = 1;
	}
	for (int i = 1; i <= n; i++) if (!num[i]) q.push(i);
	while (q.size()) {
		int x = q.front();
		q.pop();
		a.push_back(x);
		for (unsigned int i = 0; i < e[x].size(); i++) {
			int y = e[x][i];
			if (!--num[y]) q.push(y);
		}
	}
	for (int i = 1; i <= n; i++) b[i][i] = 1;
	for (int i = a.size() - 1; i >= 0; i--) {
		int x = a[i];
		for (unsigned int j = 0; j < e[x].size(); j++)
			b[x] |= b[e[x][j]];
		ans[x] = b[x].count();
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << endl;
	return 0;
}