本章节开始的所有图和树,如果没有额外声明,都是采用邻接表存储的,点的下标为
,无向边存储以两条有向边等价存储
树的深度优先遍历
深度优先遍历,就是在每个点
上面对多条分支时,任意选一条边走下去,执行递归,直到回溯到点
后,再考虑走向其他边
void dfs(int x)
{
v[x] = 1; //记录点 x 被访问过, v 是 visit 的缩写
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue; //点 y 已经被访问过
dfs(y);
}
}
这段代码访问每个点和每条边
次,其时间复杂度为
,其中
为点数,
为边数
以该段代码作为框架,我们可以统计许多关于树和图的信息
图的连通块划分
树的深度优先遍历,每从
开始一次遍历,就会访问
能够到达的所有点和边
因此通过多次深度优先遍历,可以划分出一张无向图中的各个连通分块
同理对一个森林进行深度优先遍历,可以划分出森林的每一棵树
void dfs(int x)
{
v[x] = cnt;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(y);
}
}
// main 函数下
for (int i = 1; i <= n; i ++ )
{
if (!v[i])
{
cnt ++ ;
dfs(i);
}
}
时间戳
按照上述深度优先遍历的过程,以每个节点第一次被访问(v[x]
被赋值为 1
时)的顺序
依次给这
个点
的整数标记,该标记就被称为 时间戳,记为
树的 DFS 序
一般来讲,对树进行深度优先遍历时,对于每个结点,在 刚进入递归后 和 即将回溯前 各记录一次该点的编号
最后产生的长度为
的结点序列就称为 树的 DFS 序
void dfs(int x)
{
a[ ++ m] = x; // a数组存储DFS序
v[x] = 1; // 记录点x被访问过
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(v[y]);
}
a[ ++ m] = x;
}
DFS 序 的特点是:每个节点
的编号在序列中恰好出现两次
设这两次出现的位置为
和
,则闭区间
就是以
为根的子树的 DFS 序
这样做,使得我们在很多与树相关的问题中,可以通过 DFS 序把子树统计转化为序列上的区间统计
这也是树链剖分的基本思想:将树上路径问题,剖分为多个线段来维护,不过树剖的 dfs 序是要求是重轻儿子 dfs 序
此外,二叉树的先序、中序和后序遍历,也是通过深度优先遍历产生的,由于很简单,就不具体展开了
树中各个结点的深度是一种 自顶向下 的统计信息,起初已知根节点的深度为 0
若结点
的深度为
,则他的子节点
的深度为
在深度优先遍历的过程中,结合自顶向下的递推,就可以求出每个结点的深度
请读者列举还有哪些信息一般是 自顶向下 进行统计的
void dfs(int x)
{
v[x] = 1;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[x];
if (v[y]) continue;
d[y] = d[x] + 1; // 总父节点 x 到子节点 y 递推,计算深度
dfs(y);
}
}
也有许多信息是 自底向上 进行统计的,比如以每个结点
为根的子树大小
:
对于叶子结点,我们已知 “以它为根的子树” 大小为
若结点
有
个子节点
,并且以
为根的子树大小分别是
则以
为根节点的子树大小就是
请读者列举还有哪些信息一般是 自底向上 进行统计的
对于一个结点
,如果我们把它从树中删除,那么原来的一棵树可能分成若干个不相连的部分,其中每一部分都是一棵子树
设
表示在删除结点
后产生的子树中,最大的一棵的大小
使
函数取到最小值的结点
就称为整棵树的 重心
通过如下代码,可以求出树的重心:
void dfs(int x)
{
v[x] = size[x] = 1; // 子树 x 的大小
int max_part = 0; //删掉 x 后分成的最大子树的大小
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(v[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 记录了重心
}
}
树与图的广度优先遍历需要使用一个队列来实现,起初队列中仅包含一个起点
在广度优先遍历中,不断从队头取出一个结点
,对于
面对多条分支,把沿着每条分支到达的下一个结点(如果未被访问过)插入队尾
重复执行上述过程,直到队列为空
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 = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (d[y]) continue;
d[y] = d[x] + 1;
q.push(y);
}
}
}
其中,
为点
在树中的深度,也可以在图中的层次(从起点
走到点
需要经过的点数)
广度优先遍历是一种按照层次顺序进行访问的,它具有如下两个重要性质:
层结点后,才会开始访问第
层结点
该性质会在后续章节 0x26 “广搜变形” 中再次提及并探讨
广度优先遍历的时间复杂度和深度优先遍历一样,为
拓扑排序
给定一个有向无环图DAG,若一个图中所有点构成的序列
满足:对于图中的每条边
,
在
中都出现在
之前,则称
是该有向无环图顶点的一个 拓扑序,求解序列
的过程就称为 拓扑排序
拓扑排序的思想:不断选择图中入度为
的结点
,然后把
连向的点的入度减
于是可以结合广度优先遍历的框架来高效的实现这个过程:
,起初把所有入度为
的点入队
,把
加入拓扑序列
的末尾
出发的每条边
,把
减
,若被减为
,则把
入队
即为所求
拓扑排序可以检测 “一个有向图是否有环”:对任意有向图执行上述拓扑排序,完成后检查
序列的长度,若长度小于图中点的数量,则说明某些节点未被遍历,进而说明图中存在环
void add(int x, int y)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
deg[y] ++ ;
}
void topsort()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
if (!deg[i])
q.push(i);
while (q.size())
{
int x = q.front(); q.pop();
a[ ++ cnt] = x;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if ( -- deg(y) == 0)
{
q.push(y);
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
int x, y;
cin >> x >> y;
add(x, y);
}
topsort();
for (int i = 1; i <= n; i ++ )
cout << a[i] << " ";
return 0;
}
给定一张
个点
条边的有向无环图,分别统计从每个点出发能够到达的点的数量。
输入格式
第一行两个整数
,接下来
行每行两个整数
,表示从
到
的一条有向边。
输出格式
输出共
行,表示每个点能够到达的点的数量。
数据范围
输入样例:
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
输出样例:
1
6
3
3
2
1
1
1
1
1
如果这是一棵树,则每个结点有且仅有一个前驱父节点,因此对于一个结点的两棵子树,他们的子节点不可能有交集。于是可以直接用
表示当前子树中的节点个数,进行统计。 但是本题研究对象是有向无环图,可能存在某个结点的前驱有多种情况,于是上述方法不能使用,因此考虑用状态来表示结点可达的集合
设从点
能到达的点构成的结合为
,则有递推式:
从
出发能够到达的结点,是从
的所有后继结点
出发能够到达的点的并集,再加上
自身
所有在计算所有后继结点的
值之后,就可以计算出该点的
值
这启发我们用拓扑排序算法求出一个拓扑序,然后按照拓扑序的逆序进行计算(因为在拓扑序中,对任意一条边
,
都排在
之前)
关于状态存储,由于至多有
个点要存储,即
个二进制位,而一个 unsigned int
有
位
因此一个点的状态需要
个 unsigned int
来存储,即设计数组 f[N][N / 32 - 1]
来存储状态
为了方便统计,考虑用 STL 的 bitset
来实现这
个二进制位的存储
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
deg[b] ++ ;
}
void topsort()
{
int hh = 1, tt = 0;
for (int i = 1; i <= n; i ++ )
if (!deg[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int x = q[hh ++ ];
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if ( -- deg[y] == 0)
q[ ++ tt] = y;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
topsort();
for (int i = n; i; i -- )
{
int x = q[i];
f[x][x] = 1;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
f[x] |= f[y];
}
}
for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count());
return 0;
}