图论算法模块 #

图的遍历 #

LG P2853 [USACO06DEC] Cow Picnic S #

给定 $n$ 点 $m$ 条边的无权有向图，有 $k$ 只奶牛在各自的节点上，问有多少节点，是所有奶牛都可到达的 $1 \leq n \leq 10^3, 1 \leq m \leq 10^4, 1 \leq k \leq 100$

• 反向建边 + dfs

LG P3916 图的遍历 #

给定 $n$ 点 $m$ 条边的无权有向图，求每个节点能到达的节点的最大编号 $1 \leq n, m \leq 10^5$

• 反向建边 + 从大到小dfs

拓扑排序 #

LG P4017 最大食物链计数 #

给定 $n$ 点 $m$ 条边的有向无环图，求从入读为 0 到出度为 0 的路径的数量 $1 \leq n \leq 5 \times 10^3, 1 \leq m \leq 5 \times 10^5$

• 最简单的Dag-DP

最短路 #

小白月赛123 D 春日影 #

一个 $n$ 节点 $m$ 条边的带非负边权无向图，求从 $1$ 到 $n$ 的最短路，但是允许做任意次操作，从一个节点出发到邻接点再回来，可以立刻免费的走一条边，注意是立即生效，不可达返回 $-1$ $2 \leq n, m \leq 2 \times 10^5$

• 贪心的想必然是花费最小邻边两倍权值和直接选择之间取小进行dijkstra，也可以建新边后直接跑最短路

LG P4568 [JLOI2011] 飞行路线 #

给定 $n$ 点 $m$ 条边的正权无向图，给定 $k$ 值，表示允许零代价走 $k$ 次边，问从 $0$ 到 $n - 1$ 的最短路，保证存在路径 $2 \leq n \leq 10^4, 1 \leq m \leq 5 \times 10^4, 0 \leq k \leq 10$

• 分层图最短路模板

LG P1462 通往奥格瑞玛的道路 #

给定 $n$ 点 $m$ 条边的无向图，每经过一个点需要金币 a_i，每经过一条边需要血量 w_i，现在你的总血量为 b，现在从节点 1 到 n 要求血量不能掉为负数，求路径中花费金币最大值的最小值，或者返回不能到达 $1 \leq n \leq 10^4, 1 \leq m \leq 5 \times 10^4, 1 \leq b, a_i, w_i \leq 10^9$

LG P1073 [NOIP 2009 提高组] 最优贸易 #

给定 $n$ 点 $m$ 条边，同时存在无向边和有向边，每一个点有一个权值 $w_i$，你现在从节点 $1$ 走到 $n$，可以在路径中有先后的选择两个节点 $u, v$，获得权值 $w_v - w_u$，也可以不操作，请问能获得的最大权值，保证存在路径从 $1$ 到 $n$ $1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq w_i \leq 100$

• 两种做法分层图 + 最长路或者targan缩点 + Dag-DP
• 我第一次写最长路，是让边权取负 + spfa

#

差分约束 #

LG P4878 [USACO05DEC] Layout G #

给定数轴 n 个点，编号分别为 $1, 2 \dots n$，点可以重合（距离为 $0$），要求点先后顺序不变，现给定 m1 组条件要求给定两点距离不超过 $u_i$，又给定 m2 组条件按要求两点距离不小于 $v_i$，若不存在满足条件的站位，输出 $-1$，若存在，如果点n和点1的距离最大可达无穷大，输出 -2，否则输出这个最大距离 $1 \leq n, m_1, m_2 \leq 10^4$

• 基于模板有两个转化，其一是由于相邻点有相互关系，这一条件需要建边；其二是需要判断是否为无穷大，需要跑两次SPFA分别判定（怎么做？为什么？）

同余最短路 #

较模板的题目有 LG P3403 跳楼机 和 LG P2662 [WC2002] 牛场围栏

ABC077 D - Small Multiple #

给定 $k$，求 $k$ 的倍数中数位和最小的数字，给出其数位和即可 $1 \leq k \leq 10^5$

• 神奇的转化，把问题转化为图上问题，可以用 01BFS 或者 dijkstra 解决

LG P2371 [国家集训队] 墨墨的等式 #

给定一个 $n$ 元数组 $a_i$，问 $n$ 元线性不定方程 $\sum_{i = 1}^{n} a_i x = b$ 有非负整数解时，$b$ 在给定区间 $[l, r]$ 中有多少满足条件 $1 \leq n \leq 12, 0 \leq a_i \leq 5 \times 10^5, 1 \leq l \leq r \leq 10^{12}$

• 不定方程非负整数解和完全背包有联系，从而会和同余最短路有关
• 也可以试着使用两次转圈法优化掉 log

欧拉路径 #

LG P1127 词链 #

给定 $n$ 个小写字母组成的字符串，问能否通过 ‘.’ 将所有字符串串起来，并使得 ‘.’ 连接处的两个字符(即一个字符的头和另一个的尾)，必须要相同，求满足条件的字典序最小的串或者返回不可构造 $1 \leq n \leq 1000, 1 \leq |s_i| \leq 20$

• 以字符为点，字符串为有向边做一个欧拉路径的搜索即可，注意需要判定图是否连通

LG P1341 无序字母对 #

给定 $n$ 个不重复的由两个小写字母或大写字母组成的字符串，构造一个长度为 $n + 1$ 的字符串使得任意一个长度为 $2$ 的子串在无序下都和给定若干串对应或者返回不可构造 $n$ 的范围在题设限制下可以确定

• 在上个题基础上换成了无向图欧拉路径即可

de Bruijn序列 #

我们知道限制字符种类为 $k$ 种下，长度为 $n$ 的字符串(也可以是 $k$ 进制的 $n$ 位数)一个有 $k^n$ 个，我们现在希望构造最短的字符串使得这所有的 $k^n$ 个字符串都是构造串的连续字串

不难看出这个字符串长度有个下界是 $k^n - n + 1$，要取到这个下界意味着所有 $n$ 元字串恰好不重复的组成所有种类，下面我们可以证明这是可以做到的

我们构造一个有向图，考虑所有长度为 $n - 1$ 的这类字符串，作为一个图的顶点，共 $k^{n - 1}$ 个顶点，定义有向边边权为 $k$ 种字符中一个，其连接的两个顶点满足终点字符串是起点字符串结尾接上边权字符并去掉第一个字符得到的字符串

首先不难注意到每一个点的入度和出度都是 $k$，且这个图强连通，于是这个图存在欧拉回路，起点可以任意选择一个顶点开始，我们规定结果字符串首先取为起始顶点，欧拉回路的过程中每经过一条边就接在结果字符串后面，即可得到长度为 $k^n - n + 1$ 的最终答案

下面的相关题目中都是基于数字的，要求字典序最小可以从最小节点开始并优先走边权字典序最小的边 第三个题要求构造的字符串是一个循环字符串且字典序最小，这样的最短长度就是 $k^n$，在原始答案最后删掉 $n - 1$ 个字符就是满足条件的最小字符串

相关题目： LC cracking-the-safe Poj 1780 所有可能的密码串 LG P10950 太鼓达人

欧拉回路的另一个应用是在图分解中，我们对于欧拉图，我们可以分解成若干边不相交的简单回路

LG P3520 [POI 2011] SMI-Garbage #

给定一张 $n$ 顶点 $m$ 条边的无向图，其中每条边都有一个 $0/1$ 的标记，你需要构造最少的回路使得标记为 $0$ 的边经过偶数次，标记为 $1$ 的边经过奇数次或者返回不可构造 $1 \leq n \leq 10^5, 1 \leq m \leq 10^6$

• 首先我们需要分析出如下性质：在最少回路限制下，标记为 $0$ 的边是不需要走的，标记为 $1$ 的边只需要恰好经过一次
• 于是我们只对需要经过的边保留，在每一个连通块上由于我们保证每条边只经过一次，于是只需判断每个连通块是否都存在欧拉回路，并将回路分解为若干连通块即可

2025武汉邀请赛 E. Colorful Graph #

给定一个 $n$ 节点 $m$ 条边的简单无向图，不保证连通，现要给每条边染上颜色，颜色用 $1$ 到 $m$ 的数字表示，要求和一个点直接相连的所有边中同一种颜色不超过两个点，定义关于一个点 $n$ 的直接相连的边颜色种类数为 $f(n)$，构造一种染色方案使得 $\sum_{i = 1}^n f(i)$ 最小 $2 \leq n \leq 2 \times 10^5, 1 \leq m \leq min(2 \times 10^5, \frac{n(n - 1)}{2})$

• 要求一个点周围同一种颜色的点不超过两个，定义一个点的度为 $d(i)$，不难看出我们有一个下界是 $\sum_{i = 1}^n\lceil \frac{d(i)}{2} \rceil$，我们下面构造式的证明可以做到这个下界
• 对于全偶度点的无向图，这样的图有欧拉回路所以等价于可以分解成若干边不相交的简单环，这样对每一个环染色就显然是取到下界的
• 对于有奇度点的图，首先奇度点的个数必为偶数，这样的点在计算答案时会向上取整，所以我们可以使得奇度点两两相连即转化为了全偶度点的图且不改变答案
• 具体实现是把奇度点相连时可能会破坏简单图性质，导致不能用点访问边，这样欧拉回路path里需要放边，我实现的比较困难

CF1081 E. Swap to Rearrange #

给定两个 $n$ 元数组 $a_i, b_i$，你可以进行任意次数的操作使得 $a_i$ 和 $b_i$ 交换，问最终经过若干次操作能不能使得 $a$ 是 $b$ 的重排，若可以还需要给出具体操作方案(注意不需要使得操作次数最小) $1 \leq n \leq 10^6, 1 \leq a_i, b_i \leq 10^6$

• 首先考察桶，若某个数出现的次数是奇数，那么就是不可构造
• 我们转化为图论问题，我们使得值域上的值为顶点 $a_i$ 和 $b_i$ 间建立一条无向边，如果现在给这些边标定方向成为有向边，视为起点为这个数在 $a$ 数组里，终点为在 $b$ 数组里，那么问题转为给这些边标定方向使得每一个点的入度等于初度，又由于度都为偶数，我们按照每一个连通分量里的选择一个欧拉回路标定方向即可完成

LG P3443 [POI 2006] LIS-The Postman #

给定一个 $n$ 节点 $m$ 条边的简单有向图，给定 $t$ 组点列，每组点列有 $k_i$ 个点，询问是否能构造出满足下列条件的路径或者返回不可构造

1. 从节点 $1$ 出发，在节点 $1$ 结尾
2. 每条边都恰好经过一次
3. 对于路径上依次遇到的点，也构成是一个点列，所有 $t$ 组点列都是路径上的一个连续子列

$2 \leq n \leq 5 \times 10^4, 1 \leq m \leq 2 \times 10^5, 0 \leq t \leq 10^4, 2 \leq k \leq 10^5, \sum k_i \leq 10^5$

• 对于前两个条件即是说寻找到一条节点 $1$ 出发的欧拉回路，主要是如何处理条件3
• 这些点列可能互相有连接，所以首先使用并查集或者类似链表的手段把这些点列的包含的边分为若干连续的路径，我们把这些路径缩短成一条边形成新图(注意到这里可能形成独立点，但这些点对欧拉回路来说没有影响)，在新图上进行欧拉回路，最后把缩短的边还原为原始边即可
• 上面的分析中我们没有讨论无解的情况，这里单独讨论
  1. 首先点列上相邻的点间需要存在边连接
  2. 点列连接形成的路径不能有分叉不能有环
  3. 新图需要存在欧拉回路
  4. 欧拉回路还原后包含了原始图中所有边

LG P6628 [省选联考 2020 B 卷] 丁香之路 #

tarjan专题 #

强连通分量与缩点 #

分为两部分，第一部分是直接找到每一个强连通分量或者缩点直接分析dag性质的题

LG P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G #

给定一个 $n$ 个点 $m$ 条边的有向图，问有多少个节点是所有点都可以到达的 $1 \leq n \leq 10^4, 1 \leq m \leq 5 \times 10^4$

• 考察缩点后的dag上，出度为 $0$ 的点只能有一个点，答案即为这个点在原图中的size，否则答案为 $0$

LG P2002 消息扩散 #

给定一个 $n$ 个点 $m$ 条边的有向图，问至少需要选择多少个点作为起点能使得从这些起点出发能到达所有点 $1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5$

• 计算缩点后的dag上入度为 $0$ 的点的个数

LG P2812 校园网络【[USACO]Network of Schools加强版】 #

给定一个 $n$ 个点 $m$ 条边的有向图，问至少需要选择多少个点作为起点能使得从这些起点出发能到达所有点，进一步问至少需要添加几个点才能使得只需要一个起点出发能到达所有点 $1 \leq n \leq 10^4, 1 \leq m \leq 10^6$

• 第一问和上一个题是同一个题，主要分析第二问
• 第二问等价于要使得整个有向图强连通最少需要添加多少条边，我们考虑在原图缩点后的dag上分析，入度为 $0$ 和出度为 $0$ 的点显然需要我们终点关注，我们可以构造性的证明最终的答案即是两类点数目的最大值，具体构造这里不给出

LG P1262 [POI 1996 R3] 间谍网络 #

给定一个 $n$ 个点 $m$ 条边的有向图，其中的 $p$ 个点是可以选择的，其余是不可选择的，选择每个可被选择的点都有一个代价 $a_i$，问最少需要多少代价能使得从所有选择的点出发能到达所有的点，或者返回不能满足条件并输出总是不能到达的点中编号最小的 $1 \leq p \leq n \leq 3000, 1 \leq m \leq 8000, 1 \leq a_i \leq 2 \times 10^4$

• 认为不可选择的点权值是无穷大，缩点后使得新节点为强连通分量中代价最小值，分析入度为 $0$ 的若干点是否都可以被选到即可

CF244 div2 C. Checkposts #

给定一个 $n$ 个点 $m$ 条边的有向图，每个点有一个权值 $a_i$，选择一个点能控制和它强连通的所有点，问最小的总权值代价使得所有点都被控制，并且计算在这个最小代价下的方案数 $1 \leq n \leq 10^5, 0 \leq m \leq 3 \times 10^5, 1 \leq a_i \leq 10^9$

• 缩点后计算每个强连通分量的最小权值以及最小权值的节点个数做统计即可

LG P10944 Going from u to v or from v to u? #

给定一个 $n$ 个点 $m$ 条边的有向图，判断这个图是否满足从任意两个节点 $u, v$ 都有从 $u$ 到 $v$ 存在路径或 $v$ 到 $u$ 存在路径 $1 \leq n \leq 1000, 1 \leq m \leq 5999$

• 分析知缩点后判断dag是否为一条链即可，注意特判

P1407 [国家集训队] 稳定婚姻 #

初始时 $2n$ 个点的二分图匹配，每一部都有 $n$ 个节点，共 $n$ 条匹配边，保证所有点都参与。接下来给定关于这 $2n$ 个点的 $m$ 条新边，保证新边都是连接两个部的边，询问去掉每一个原始匹配边，使用若干新关系或其余匹配便能否使得所有点再次完成匹配 $1 \leq n \leq 4000, 1 \leq m \leq 2 \times 10^4$

• 考虑一种建图，初始图可以视为一个二分图，我们将点集分为两部分，使得边建立为有向边从第一部分到第二部分，新边建立有向边从第二部分到第一部分，这样考虑去掉一个初始匹配边时，只需要判断两个点是否在同一个强连通分量即可

第二部分是需要缩点后对dag进行dp等操作的题

LG P2656 采蘑菇 #

给定一个 $n$ 个点 $m$ 条边的有向图，每条边都有一个边权 $w_i$ 和一个损失系数 $t_i$，给定起点 $s$ 不限定终点的情况下，每次经过一条边可以获得这条边的权值，该边的权值同时会更新为 $\lfloor w_i \cdot t_i \rfloor$，求获取的最大值 $1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 10^6, 0 \leq t_i \leq 0.8$，保证最多一位小数

• 缩点后进行dag-dp，注意强连通分量中的边可以无限次经过，dag上的边只能最多经过一次
• 这里是固定起点的dag-dp，可以建立反图做常规拓扑排序或者进行dfs
• 注意由于一位小数可以避免浮点数问题，这里直接用浮点会WA

LG P3627 [APIO2009] 抢掠计划 #

给定一个 $n$ 个点 $m$ 条边的有向图，每个节点有点权 $w_i$，给定起点 $s$ 和若干可能的终点，每经过一个节点可以获得其点权，每个点的点权只能在第一次经过时获取，问从起点出发到任意终点能获取的最大点权和 $1 \leq n, m \leq 5 \times 10^5, 0 \leq w_i \leq 5000$

• 同上一个题，缩点后转化为固定起点和若干终点的dag-dp，我想到的做法是一个回溯的dfs写法，不清楚有没有简单写法

LG P1073 [NOIP 2009 提高组] 最优贸易

这个题最短路部分讲过，也可以使用tarjan缩点做

LG P2272 [ZJOI2007] 最大半连通子图 #

给定一个 $n$ 个点 $m$ 条边的有向图，定义两个点 $u, v$ 半连通为从 $u$ 出发能到 $v$ 或 $v$ 出发能到 $u$，半连通子图定义为一个子图满足任意两个点都半连通，求最大的半连通子图(含的节点数最多)所包含的节点数及该子图的数量 $1 \leq n \leq 10^5, 1 \leq m \leq 10^6$

• 在前面 Going from u to v or from v to u? 这个题中我们分析过同样的性质，即半连通子图是一个强连通分量的链，于是我们缩点后即转化为dag上点权和最长链的长度以及数量，进行一个dp即可
• 注意因为要计数所以新图要去掉重边

LG P2169 正则表达式 #

给定一个 $n$ 个点 $m$ 条边的有向图，每条边都有一个边权 $w_i$，在一个强连通分量内移动不消耗边权，问从节点 $1$ 到节点 $n$ 的最短路 $1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 10^6$

• 缩点后进行dijkstra即可

LG P2515 [HAOI2010] 软件安装 #

给定一个 $n$ 个点 $n$ 条边的有向图，保证每个节点的入度为 $0$ 或者 $1$，每个节点有一个重量 $w_i$ 和权值 $v_i$，给定背包容量 $m$，要求一个节点产生价值当且仅当所有能到达该节点的点都装进背包，求背包能装下的最大价值 $0 \leq n \leq 100, 0 \leq m \leq 500, 0 \leq w_i \leq m, 0 \leq v_i \leq 1000$

• 首先图构成一个内向基环树森林，在这个图上直接做dp是比较困难的，我们注意到对一个环上的点来说所有点要么同时选要么同时不选，所以进行缩点，即变成一个森林
• 我们建立虚点连接森林的所有根节点转化为一个经典的树上背包
• 对于这个树上背包最优解是基于dfn的 $O(mn)$ 的做法，所以这个题的数据事实上是弱的

LG P3275 [SCOI2011] 糖果 #

$n$ 个变量要求满足 $m$ 组不同类型的不等或相等关系，假设每次给定变量 $x_i, x_j$，具体有以下 $5$ 种类型

1. $x_i = x_j$
2. $x_i < x_j$
3. $x_i \geq x_j$
4. $x_i > x_j$
5. $x_i \leq x_j$

要求所有变量取正整数，问所有变量和最小是多少或者返回不存在满足条件的赋值 $1 \leq n, m \leq 10^5$

• 使用差分约束的思想建立一个边权仅为 $0$ 或 $1$ 的有向图，注意到对于一个强连通分量，如果有边权为 $1$ 的边就不可满足该条件
• 于是一个强连通分量的值取值相等，缩点后设置入度为 $0$ 的点为 $1$ 进行dag-dp即可

LG P4819 [中山市选] 杀人游戏 #

给定一个 $n$ 个点 $m$ 条边的有向图，存在随机的一个点是标记点，每次可以选择一个点使得从这个点出发能到达的点都确定是否为标记点，但如果直接选中标记点就失败，问成功确定标记点而没有直接选中标记点的概率在最优策略下的概率是多少 $1 \leq n \leq 10^5, 0 \leq m \leq 3 \times 10^5$

• 观察到对于一个强连通分量最多选择一个点且选择哪个点实际上都是均等的，所以考虑缩点，对于相连的强连通分量我们选择路径上更靠前的会更优
• 于是我们可以发现，一般情况下我们可以选择缩点后入度为 $0$ 的点选择一个可以覆盖所有点，但需要注意一个特殊情况，如果有孤立点，或者这个点(它本身恰好是一个强连通分量)连接的强连通分量都能被别的覆盖，那么这个点我们可以不选，就省下一个点，计算概率直接用不需要选择的点除以所有点即可
• 最后需要注意 $n = 1$ 有一个特判

割边与边双连通分量缩点 #

第一部分是关于割边和边双连通分量的直接分析

CF89 div2 E. Bertown roads #

给定一个 $n$ 个点 $m$ 条边的无向连通图，先要求给每条边标定方向使得变成有向图，问能否使得有向图强连通，如果可以就给出一个构造 $1 \leq n \leq 10^5, 1 \leq m \leq 3 \times 10^5$

• 首先如果有割边就是不可构造的，而且这是充要的，我们回顾tarjan的过程进行dfn树的遍历的边就规定像下，而回溯的边规定向上，于是就完成了构造

LG P7687 [CEOI 2005] Critical Network Lines #

给定一个 $n$ 个点 $m$ 条边的无向连通图，存在两种信号源，第一种信号有 $k$ 个节点，第二种信号有 $l$ 个节点。源节点可以通过边给其余节点提供信号（包括自己），每个节点必须要接受到两种不同信号，现在可以切断一条边，问有多少条边能够使得切断后存在某些点不能同时接受到两种信号 $1 \leq n \leq 10^5, 1 \leq m \leq 10^6$

• 首先满足条件的边只能是割边，但并不是充分的，如果切断割边产生的不同连通块，同时存在两种信号源则这个割边是无效的
• 于是我们可以在进行tarjan的dfs树上进行树上dp，对割边处下方子树的两种信号源个数做分析即可

LG P2860 [USACO06JAN] Redundant Paths G #

给定一个 $n$ 个点 $m$ 条边的连通无向图，问至少需要添加多少条边使得整个图边双连通 $1 \leq n \leq 5 \times 10^3, 1 \leq m \leq 10^4$

• 充分必要性分析即可放缩出答案，结论题

hdu2460 Network #

给定一个 $n$ 个点 $m$ 条边的连通无向图，给定 $q$ 次加边，查询每次加边后割点的数量 $1 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5, 1 \leq q \leq 10^4$

• 缩点为一棵树，我们认定一个节点作为根转化为有根树，预处理深度和父节点，对每个节点建立一个并查集，每次加边时如果不在一个连通块里就每次把深度大的节点向上跳依次合并节点到LCA为一个连通块即可维护出割点的数量

割点与点双连通分量缩点 #

loj 10103. 「一本通 3.6 练习 4」电力 #

给定一个 $n$ 个点 $m$ 条边的无向图，问在删除一个点及其相连的边的情况下能得到的最大连通块数量 $1 \leq n \leq 10^4$

• 在进行tarjan时维护这个割点对应的连通块个数，取最大的节点计算即可

LG P5058 [ZJOI2004] 嗅探器 #

给定一个 $n$ 个点 $m$ 条边的无向连通图，给定两个不同的节点 $x, y$ 问有多少种方案使得删除一个非 $x, y$ 的节点及其相连边能使得 $x, y$ 不连通 $1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 5 \times 10^5$

• 首先我们选择的一定是割点，但不是所有的都是，我们从 $x$ 节点进行tarjan，要求割点下方对应的子树需要包含 $y$ 节点，可以使用dfn的相对大小判断。具体来说，假设割点 $u$ 以及对于切割出连通块的边为 $u-v$ 那么需要有 $dfn(y) \geq dfn(v)$，注意并不是 $dfn(y) > dfn(u)$ 为什么？

LG P3225 [HNOI2012] 矿场搭建 #

给定一个 $n$ 个点 $m$ 条边的无向连通图，问至少需要给标记多少个节点，才能使得任意删除一个点及其相连的边的情况下所有其余点出发都能到达一个标记点，并求出做到最小标记个数的方案数有多少种 $1 \leq n \leq 500, 1 \leq m \leq 10^3$

• 分析可知每次断一个点只有在断开割点时才可能改变连通性，于是对于对应点双连通分量中仅一个割点的分量一定需要一个非割点位置的标记，而对于有多个割点的点双连通分量，则就不需要进行标记了
• 但需要注意整个图都是点双连通分量的情况，而且这时候至少需要选择两个点标记。故而加入推广到不连通图，要考虑每一只分量的割点是否为 $0$ 的情况