正睿OI Day15 总结

强连通分量

这个以前学了很久了，在这里就不在赘述。直接上题目吧。

T1

题目

$C $国有$ n $个大城市和$ m$ 条道路，每条道路连接这 $n$个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1 $条。

$C $国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 $C$ 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 $C$ 国 n 个城市的标号从 $1~ n$，阿龙决定从 $1 $号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 $n$ 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 $C $国有 $5$个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设 $1~n$ 号城市的水晶球价格分别为 $4,3,5,6,1$。

阿龙可以选择如下一条线路：$1$->$2$->$3$->$5$，并在 $2 $号城市以$ 3$ 的价格买入水晶球，在 $3$号城市以$ 5 $的价格卖出水晶球，赚取的旅费数为 2。

阿龙也可以选择如下一条线路$ 1$->$4$->$5$->$4$->$5$，并在第$1 $次到达$ 5$ 号城市时以 $1 $的价格买入水晶球，在第 $2$ 次到达$ 4$ 号城市时以$ 6$ 的价格卖出水晶球，赚取的旅费数为$ 5$。

现在给出 $n $个城市的水晶球价格，$m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

思路

这个题目非常经典。

在本题中，可以将双向边看成两条有向边。

注意到在一个强连通分量中，可以在城市之间任意移动。我们可以将强连通分量缩成一个点，保留其中最大和最小的价格，记为mx(u) 和mn(u)。

缩完点之后，原图变成了一个DAG（有向无环图），我们可以拓扑排序后进行DP。设f(u)是从点1 到达点u 的最大利润。转移如下：

$mn(u) ← min(mn(u), mn(v)), for each (v, u) ∈ E$

$f(u) ← max(f(u), f(v)), for each (v, u) ∈ E$

$f(u) ← max(f(u), mx(u) − mn(u))$

然后这个题利用一个性质可以优化：

Tarjan 算法找到强连通分量的顺序翻转后是一个拓扑序。

这个东西其实只要记住就可以了。

双连通分量

定义

在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 $u$ 和 $v$ 边双连通。

在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪个点（只能删去一个，且不能删 $u$ 和 $v$ 自己）都不能使它们不连通，我们就说 $u$ 和 $v$ 点双连通。

边双连通具有传递性，即，若 $x,y$ 边双连通，$y,z$ 边双连通，则 $x,z$ 边双连通。

点双连通 不 具有传递性，反例如下图，$A,B$ 点双连通，$B,C$ 点双连通，而 $A,C$ 不 点双连通。

桥：如果一条边删除后使得原图不连通，则称其为桥（bridge）。如果不是连通图，我们也可以定义桥为删除后使得连通分量数增加的边，也就是其所有连通分量的桥。

边双连通图缩点后就是一个点，也就没有桥。

DFS 找桥并判断边双连通

首先，对原图进行 DFS。

如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖，黑色的树边不被 任何 非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

如何用算法去实现以上过程呢？首先有一个比较暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，这样的时间复杂度为 $O(nm)$。

怎么优化呢？可以用差分。对于每一条非树边，在其树上深度较小的点处打上 -1 标记，在其树上深度较大的点处打上 +1 标记。然后 $O(n)$ 求出每个点的子树内部的标记之和。对于一个点 $u$，其子树内部的标记之和等于覆盖了 $u$ 和 $u$ 的父亲之间的树边的非树边数量。若这个值非 $0$，则 $u$ 和 $u$ 的父亲之间的树边不是桥，否则是桥。

用以上的方法 $O(n+m)$ 求出每条边分别是否是桥后，两个点是边双连通的，当且仅当它们的树上路径中 不 包含桥。

圆方树

简介

众所周知，树（或森林）有很好的性质，并且容易通过很多常见数据结构维护。

而一般图则没有那么好的性质，所幸有时我们可以把一般图上的某些问题转化到树上考虑。

而圆方树（Block forest 或 Round-square tree）就是一种将图变成树的方法。本文将介绍圆方树的构建，性质和一些应用。

定义

圆方树最初是处理“仙人掌图”（每条边在不超过一个简单环中的无向图）的一种工具，不过发掘它的更多性质，有时我们可以在一般无向图上使用它。

要介绍圆方树，首先要介绍 点双连通分量。

一个 点双连通图 的一个定义是：图中任意两不同点之间都有至少两条点不重复的路径。
点不重复既指路径上点不重复（简单路径），也指两条路径的交集为空（当然，路径必然都经过出发点和到达点，这不在考虑范围内）。

可以发现对于只有一个点的图比较难定义它是不是一个点双，这里先不考虑节点数为 $1$ 的图。

一个近乎等价的定义是：不存在割点的图。
这个定义只在图中只有两个点，一条连接它们的边时失效。它没有割点，但是并不能找到两条不相交的路径，因为只有一条路径。
（也可以理解为那一条路径可以算两次，的确没有交，因为不经过其他点）

虽然原始的定义的确是前者，但是为了方便，我们规定点双图的定义采用后者。

而一个图的 点双连通分量 则是一个 极大点双连通子图。
与强连通分量等不同，一个点可能属于多个点双，但是一条边属于恰好一个点双（如果定义采用前者则有可能不属于任何点双）。

在圆方树中，原来的每个点对应一个 圆点，每一个点双对应一个 方点。
所以共有 $n+c$ 个点，其中 $n$ 是原图点数，$c$ 是原图点双连通分量的个数。

而对于每一个点双连通分量，它对应的方点向这个点双连通分量中的每个点连边。
每个点双形成一个“菊花图”，多个“菊花图”通过原图中的割点连接在一起（因为点双的分隔点是割点）。

显然，圆方树中每条边连接一个圆点和一个方点。

下面有一张图，来自 WC 的 PPT，显示了一张图对应的点双和圆方树形态。[^ref2]

圆方树的点数小于 $2n$，这是因为割点的数量小于 $n$，所以请注意各种数组大小要开两倍。

其实，如果原图连通，则“圆方树”才是一棵树，如果原图有 $k$ 个连通分量，则它的圆方树也会形成 $k$ 棵树形成的森林。

如果原图中某个连通分量只有一个点，则需要具体情况具体分析，我们在后续讨论中不考虑孤立点。

构建

对于一个图，如何构造出它的圆方树呢？首先可以发现如果图不连通，可以拆分成每个连通子图考虑，所以我们只考虑连通图。

因为圆方树是基于点双连通分量的，而点双连通分量又基于割点，所以只需要用类似求割点的方法即可。

对图进行 DFS，并且中间用到了两个关键数组 dfn 和 low（类似于 Tarjan）。

dfn[u] 存储的是节点 $u$ 的 DFS 序，即第一次访问到 $u$ 时它是第几个被访问的节点。
low[u] 存储的是节点 $u$ 的 DFS 树中的子树中的某个点 $v$ 通过 最多一次返祖边或向父亲的树边 能访问到的点的 最小 DFS 序。
如果没有听说过 Tarjan 算法可能会有点难理解，让我们举个例子吧：

（可以发现这张图其实和上面图片中的图等价）
这里树边从上至下用直线画出，返祖边从下至上用曲线画出。节点的编号便是它的 DFS 序。

则有 low 数组如下：

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$\mathrm{low}[i]$	$1$	$1$	$1$	$3$	$3$	$4$	$3$	$3$	$7$

并不是很难理解吧，注意这里 $9$ 的 low 是 $7$，与一些求割点的做法有差异，因为为了方便，我们规定了可以通过父边向上，但主要思想是相同的。

我们可以很容易地写出计算 dfn 和 low 的 DFS 函数：

void Tarjan(int u) {
  low[u] = dfn[u] = ++dfc;   
  for (int v : G[u]) {   
    if (!dfn[v]) {     
      Tarjan(v);    
      low[u] = std::min(low[u], low[v]);  
    } else
      low[u] = std::min(low[u], dfn[v]);  
  }
}

接下来，我们考虑点双和 DFS 树以及这两个数组之间的关联。

可以发现，每个点双在 DFS 树上是一棵连通子树，并至少包含两个点；特别地，最顶端节点仅往下接一个点。

同时还可以发现每条树边恰好在一个点双内。

我们考虑一个点双在 DFS 树中的最顶端节点 $u$，在 $u$ 处确定这个点双，因为 $u$ 的子树包含了整个点双的信息。

因为至少有两个点，考虑这个点双的下一个点 $v$，则有 $u$，$v$ 之间存在一条树边。

不难发现，此时一定有 $\mathrm{low}[v]=\mathrm{dfn}[u]$。
更准确地说，对于一条树边 $u\to v$，$u,v$ 在同一个点双中，且 $u$ 是这个点双中深度最浅的节点 当且仅当 $\mathrm{low}[v]=\mathrm{dfn}[u]$。

那么我们可以在 DFS 的过程中确定哪些地方存在点双，但是还不能准确确定一个点双所包含的点集。

这并不难处理，我们可以在 DFS 过程中维护一个栈，存储还未确定所属点双（可能有多个）的节点。

在找到点双时，点双中除了 $u$ 以外的其他的点都集中在栈顶端，只需要不断弹栈直到弹出 $v$ 为止即可。

当然，我们可以同时处理被弹出的节点，只要将其和新建的方点连边即可。最后还要让 $u$ 和方点连边。

这样就很自然地完成了圆方树的构建，我们可以给方点标号为 $n+1$ 开始的整数，这样可以有效区分圆点和方点。

void Tarjan(int u) {
  printf("  Enter : #%d\n", u);
  low[u] = dfn[u] = ++dfc;                // low 初始化为当前节点 dfn
  stk[++tp] = u;                          // 加入栈中
  for (int v : G[u]) {                    // 遍历 u 的相邻节点
    if (!dfn[v]) {                        // 如果未访问过
      Tarjan(v);                          // 递归
      low[u] = std::min(low[u], low[v]);  // 未访问的和 low 取 min
      if (low[v] == dfn[u]) {  // 标志着找到一个以 u 为根的点双连通分量
        ++cnt;                 // 增加方点个数
        // 将点双中除了 u 的点退栈，并在圆方树中连边
        for (int x = 0; x != v; --tp) {
          x = stk[tp];
          T[cnt].push_back(x);
          T[x].push_back(cnt);
        }
        // 注意 u 自身也要连边（但不退栈）
        T[cnt].push_back(u);
        T[u].push_back(cnt);
      }
    } else
      low[u] = std::min(low[u], dfn[v]);  // 已访问的和 dfn 取 min
  }
  printf("  Exit : #%d : low = %d\n", u, low[u]);
  printf("  Stack:\n    ");
  for (int i = 1; i <= tp; ++i) printf("%d, ", stk[i]);
  puts("");
}

T2

题目

给定一张 $n$ 个点 $m$ 条边的无向图，现在想要把这张图定向。

有 $p$ 个限制条件，每个条件形如 $(x_i,y_i)$，表示在新的有向图当中，$x_i$ 要能够沿着一些边走到 $y_i$​​。

现在请你求出，每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。

数据保证有解。

思路

可以得到一个的结论:在同一个双联通分量中的点之间的边方向无法确定。

所以可以缩点，然后得到一个森林。

缩点之后变成一棵树，则相当于给定了若干条树上路径，路径上的边必须和路径的方向相同。

不在任何一条路径上的边可以任意定向。

对于要求的方向，多定义一个$a$数组，对于起点$x$，$a[x]++$,终点$y$，$a[y]–$（听说这个操作叫树上差分）。

每一点走向父节点的边方向可以记住$a$来判断。

$a\leq 0$则应由父节点走向子节点

$a\geq 0$则应由子节点走向父节点

$a=0$则无法判断方向。

T3

题目

给定一张$n$ 个点$m$ 条边的简单无向连通图，点有权值。$q$ 次操作，操作有以下两种：

• 修改一个点的点权。

• 询问两点之间所有简单路径上点权的最小值。

思路

注意到在点双连通图中，对于任意的$u, v,w$，都存在从$u$ 开始经过$v$ 到达$w$ 的简单路径。

两个点$u, v$ 之间所有简单路径能经过的点，也就是在圆方树上$u$ 到$v$ 的路径上所有方点的
邻点（如果$u = v$ 那就是$u$ 自己）。

我们令一个方点的点权是其邻点点权的最小值，那么询问的答案就是圆方树上两点路径上
的点权最小值。

但方点的点权并不好维护。我们考虑维护其所有孩子的点权最小值，这样每次修改只会影响一个方点，每个方点用一个std::multiset 维护即可。容易发现这样处理之后，只有$lca(u, v)$ 是方点时其父亲没有计入答案，特殊处理一下即可。

T3

题目

有 $n$ 个骑士，有 $m$ 对骑士相互憎恨。骑士可能召开圆桌会议，骑士们围绕着圆桌而坐，需要满足

• 骑士的个数是大于 $1$ 的奇数。
• 任何相邻的一对骑士都不相互憎恨。

求有多少骑士不可能参加任何圆桌会议。

思路

1、 利用m对憎恨对构造图G，则图G中有边相连的两个点表示这2个骑士互相憎恨。

2、 构造图G的补图G，则图G中有边相连的两个点表示这2个骑士可以坐在相邻位置。

3、 在图~G中，可能存在某些点的度数<=1，就是说这些骑士旁边最多只能坐另一个骑士，根据圆桌的座位要求每个骑士k的座位两边都必定各有一个骑士（k度数==2），那么我们认为这些度数<=1的点是孤立的或者是单连通的，也就是说他们不在圆桌的“环”内。

例如上图，我们利用图G构造补图~G后，显然骑士1的度=0，他是孤立的、不连通的；骑士5的度=1，他是单连通的；骑士{2,3,4}则构成一个双连通分量，他们正在圆桌“环”内开会。显然度数<=1的骑士1和骑士5都在环外，不满足出席会议的条件，亚瑟王为了维护世界和平自然会把这2人驱逐出骑士团。

骑士在双连通分量内（在环内），并不能就此就说明它可以出席会议了，因为假如这个骑士所在的双连通分量，不是一个奇数顶点的环（奇圈），而是一个偶数顶点的环，那么这个双连通分量内的全部骑士都要被亚瑟王开除。

到这里就很显然了，求边双联通分量即可。

T4

题目

有一个岛上有 $n$ 个旅游景点，有 $m$ 条双向道路连接着它们。现在要修建一些额外的道路，使得任意一条道路封闭后游客都能从一个旅游景点到达任意的旅游景点。求最少需要修建的道路数量。

思路

题目其实就是求一个图中，至少再加上几条边，可以变成一个边双联通图。

首先缩点，整个图变成一棵树。

这里有个结论：

若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么

$至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2$。

要知道度数为1的节点总数，我们只需在SCC加边时统计即可。

T5

题目

有一张无向图，选一些点涂黑，满足任意删除一个点后（可能是被涂黑的点），每个连通分量都有至少一个黑点。求最少涂黑的点数和方案数。

思路

先讨论其中一个点双联通分量.

去掉其中一个节点 $x$ 时，只有两种情况：

点双联通分量依然是点双联通分量。

点双联通分量变成多个子点双联通分量。

对于第一种情况，剩下的任意一个点都有到其他任意一个点的路径，剩余的节点需要有一个到逃生口节点的路径。

对于第二种情况，这个去掉的点 $x$ 也叫做 割点。每个子点双联通分量都要选取一个逃生口节点。

而子联通分量中，也可能存在割点 $y$。所以每个子子联通分量也要选取一个逃生口节点。但有一个子子联通分量是包含 $x$ 这个点的，也就是说，当这个子联通分量中有一个点被去掉后，包含 $x$ 的子子联通分量有到其他子联通分量中的逃生口节点的路径，所以这个子子联通分量就不需要选取逃生口节点了。

那么也就是说，一个点双联通分量的所有割点，会把这个点双联通分量分成多个子联通分量。

当一个子联通分量只包含一个割点时，意味着必须在其中任意选取一个不是割点的点作为逃生口节点。

当一个子联通分量包含若干个割点时，不用选取逃生口节点，因为这个子联通分量任意一个点被去掉，剩下的点都有到其他子联通分量的点的路径。

对于方案数，设该子联通分量的节点数为 $size$：

$size-1$ 个不同的选取方法。

$0$ 个不同的选取方法。

$\frac{size\times(size-1)}{2}$ 个不同的选取方法。

再利用乘法原理，就可以得到方案数了。

T6

题目

给定一张有向图，求至少添加多少条边能使得其强连通。

思路

我们可以把这个没有双联通的有向图看成一个有源点和汇点的图。每个讲汇点连向源点，这一块就会变成强连通分量。所以最后输出源点和汇点数量的更大的那个就行了。

T7

题目

给定一张简单无向连通图，边权为 $0$ 或 $1$，求从 $a$ 到 $b$ 是否存在一条边权和非 $0$ 的且不经过重复边的路径。

思路

每条边最多经过$1$次

不难想到，一个环上如果有一条边为$1$，那么这个环上所有点对都是符合条件的

所以可以缩点（边双），缩点后的每个点，如果其中有一条为$1$的边，那么就把这个点的权值赋值为$1$

然后这个图就变成了一棵树

然后问题就变成了：给定树上两个点，询问他们之间的路径，是否有点或边的权值为$1$