OI-wiki 弦图（Chordal Graph）全解：完美消除序列、MCS 最大势算法与五大线性可解问题

OI-wiki 弦图（Chordal Graph）全解：完美消除序列、MCS 最大势算法与五大线性可解问题

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

弦图是一类结构优美的特殊无向图：任意长度大于 3 的环都至少有一条弦（连接环上不相邻两点的边）。正是这条看似简单的性质，使得大量在一般图上属于 NP-Hard 的问题（最大团、最小染色、最大独立集、最小团覆盖）在弦图上全部拥有$O(n+m)$ 的线性时间复杂度算法。本文以 docs/graph/chord.md 为主体，系统梳理弦图的定义与性质、点割集与单纯点理论、完美消除序列、最大势（MCS）线性判定算法，并给出极大团、色数/团数、最大独立集/最小团覆盖五大经典问题的构造方法与完整参考代码。读完本文，你将掌握弦图的完整理论脉络与可直接套用的线性算法实现。

一、弦图基础：定义与基本性质

1.1 相关图论概念

在正式定义弦图之前，先建立一组贯穿全文的图论术语（记原图为 $G=(V,E)$）：

• 子图：点集和边集均为原图点集和边集子集的图。
• 导出子图（诱导子图）：点集为原图点集子集，边集为所有满足两个端点均在选定点集中的边构成的图。导出子图完全由选点决定，不能自由增减边。
• 团：完全子图，即其中任意两点之间都有边相连。
• 极大团：不是其他团子图的团（即无法再加入任何点仍保持为团）。
• 最大团：点数最大的团。
• 团数：最大团的点数，记为 $\omega(G)$。
• 最小染色：用最少的颜色给点染色，使得所有边连接的两点颜色不同。
• 色数：最小染色所需的颜色数，记为 $\chi(G)$。
• 最大独立集：最大的点集，使得点集中任意两点都没有边直接相连。其大小记为 $\alpha(G)$。
• 最小团覆盖：用最少的团覆盖所有的点，使用的团数记为 $\kappa(G)$。

1.2 弦与弦图

• 弦：连接环中不相邻两点的边。
• 弦图：任意长度大于 $3$ 的环都有一个弦的图称为弦图。

直观理解：弦图是一类"没有大而无弦的环"的图。三角剖分图、森林、树、完全图都是弦图的典型特例。弦图的这一强结构约束，正是后续所有线性算法的根基。弦图相关前置知识可参考 docs/graph/concept.md 与 docs/graph/max-clique.md（团与最大团问题）。

1.3 四个基础引理（Lemma 1–4）

Lemma 1：团数 $\omega(G)\le \chi(G)$（色数）。

证明：单独考虑最大团的导出子图进行染色，至少需要 $\omega(G)$ 种颜色（团内任意两点相邻，必须异色）。

Lemma 2：最大独立集数 $\alpha(G)\le \kappa(G)$（最小团覆盖数）。

证明：每个团中至多选择一个点（团内两点均相邻，不能同属一个独立集）。

Lemma 3：弦图的任意导出子图一定是弦图。

证明：反证。如果弦图存在一个导出子图不是弦图，说明该导出子图上存在一个大于 $3$ 的无弦环，那么无论原图如何加边，这个无弦环都始终存在，原图不可能是弦图，矛盾。

Lemma 4：弦图的任意导出子图一定不可能是一个点数大于 $3$ 的环。

证明：点数大于 $3$ 的环不是弦图（环上不存在连接不相邻两点的弦），由 Lemma 3 直接推出。

Lemma 3 与 Lemma 4 揭示了弦图的遗传性（hereditary property），这是后续用归纳法论证"任何弦图都有单纯点"的关键。而 Lemma 1、Lemma 2 则给出了四个经典参数之间的两对"一边一界"关系，为后文证明"弦图上 $\omega=\chi$、$\alpha=\kappa$"埋下伏笔。

二、弦图的判定：问题与理论工具

2.1 问题描述

给定一个无向图 $G$，判断其是否为弦图。朴素思路是枚举所有长度大于 $3$ 的环检查弦，但环数量可能是指数级。本节将沿着"点割集 → 单纯点 → 完美消除序列"的路径，构建出线性时间判定算法。

2.2 点割集

对于图 $G$ 上的两点 $u,v$，定义这两点间的点割集为：删除这一集合后，$u,v$ 两点之间不再连通。若关于 $u,v$ 两点间的一个点割集的任意子集都不是点割集，则称这个点割集为极小点割集（注意"极小"是集合包含关系下的极小，而非点数最小）。

Lemma 5：图关于 $u,v$ 的极小点割集将原图分成了若干个连通块。设包含 $u$ 的连通块为 $V_1$，包含 $v$ 的连通块为 $V_2$，则对于极小点割集上的任意一点 $a$，$N(a)$（$a$ 的邻域）一定包含 $V_1$ 和 $V_2$ 中的点。

证明：若 $N(a)$ 只包含 $V_1$、$V_2$ 中至多一个连通块的点，则从点割集中删去 $a$ 后 $u,v$ 仍不连通，说明原点割集不是极小点割集，矛盾。

Lemma 6：弦图上任意两点间的极小点割集的导出子图一定为一个团。

证明（分情况）：

• 当极小点割集大小 $\le 1$ 时，导出子图显然是一个团。
• 否则，设极小点割集上有两点 $x,y$。由 Lemma 5，$N(x)$ 中有 $V_1,V_2$ 中的点，设为 $x_1,x_2$；同理设 $y_1,y_2$（注意可能有 $x_1=y_1,\ x_2=y_2$）。由于 $V_1,V_2$ 均为连通块，在 $x_1,y_1$ 与 $x_2,y_2$ 两个点对之间分别存在最短路径。于是图上存在一个环 $x-x_1\sim y_1-y-y_2\sim x_2-x$，该环大小一定 $\ge 4$。根据弦图定义，该环上一定存在一条弦：
  • 若这条弦连接了 $V_1,V_2$ 两个连通块，则删去点割集后 $u,v$ 仍连通，点集不是点割集；
  • 若这条弦连接单个连通块内部的两个点，或连接一个连通块内部点与点割集上的点，都会破坏最短路的性质；
  • 所以这条弦只能连接 $x,y$ 两点。

由此，弦图中每个极小点割集中的任意两点都有边直接相连，性质得证。

Lemma 6 是一个核心结构定理：弦图中"割开"任意两点的最小隔断集合本身必须是一个团，这为归纳构造单纯点提供了落脚点。

2.3 单纯点

设 $N(x)$ 表示与点 $x$ 相邻的点集。若点集 ${x}+N(x)$ 的导出子图为一个团，则称点 $x$ 为单纯点（simplicial vertex）。通俗地说，单纯点的所有邻居彼此两两相邻，即 $x$ 与它的邻居们共同构成一个团。

Lemma 7：任何一个弦图都至少有一个单纯点；不是完全图的弦图至少有两个不相邻的单纯点。

证明（数学归纳法，单独考虑每一个连通块）：

• 归纳基底：当图与完全图同构时，图上任意一点都是单纯点；当图的点数 $\le 3$ 时，引理成立。
• 若图点数 $\ge 4$ 且不为完全图，则必然存在 $u,v$ 使得 $(u,v)\notin E$。设 $I$ 是图关于 $u,v$ 的极小点割集，$A,B$ 分别是删去 $I$ 后 $u,v$ 所在的连通块。由对称性只考虑 $A$ 一侧，设 $L=A+I$：
  • 若 $L$ 为完全图，则 $u$ 为单纯点；
  • 若 $L$ 不是完全图，因为 $L$ 是原图的导出子图，由 Lemma 3 知 $L$ 也是弦图，归纳假设给出 $L$ 中至少有两个不相邻的单纯点。又因 $I$ 是一个团（Lemma 6），其上两点都相邻，所以 $A$ 中一定有一个单纯点，该单纯点扩展到全图仍为单纯点。

由于每次把图分成若干连通块证明，块的大小严格减小且都满足性质，归纳成立。

2.4 完美消除序列

令 $n=|V|$，完美消除序列（Perfect Elimination Ordering, PEO）$v_1,v_2,\ldots,v_n$ 是 $1,2,\ldots,n$ 的一个排列，满足 $v_i$ 在 ${v_i,v_{i+1},\ldots,v_n}$ 的导出子图中为单纯点。即：按序列顺序逐个删点，删到每个点时它都是剩余图的单纯点。

Lemma 8：一个无向图是弦图当且仅当其有一个完美消除序列。

充分性：点数为 $1$ 的弦图有完美消除序列。由 Lemma 3 和 Lemma 7，点数为 $n$ 的弦图的完美消除序列可以由点数为 $n-1$ 的弦图的完美消除序列加上一个单纯点得到（归纳）。

必要性：反证。假设存在无向图含有一个结点数 $>3$ 的环且拥有完美消除序列。设在完美消除序列中第一个出现的环上的点为 $v$，$v$ 在环上与 $v_1,v_2$ 相连。由完美消除序列的性质（即单纯点的定义），$v_1,v_2$ 必须直接有边相连，这与 $v_1,v_2$ 是环上不相邻两点的假设矛盾（它们之间的边正是弦）。

Lemma 8 是整篇文章的枢纽：弦图 ⇔ 存在完美消除序列。于是"判定弦图"完全转化为"求完美消除序列"与"验证序列合法性"两个子问题。

三、求完美消除序列的算法

3.1 朴素算法（$O(n^4)$）

最直观的做法完全照抄定义：

1. 每次在剩余图中找到一个单纯点$v$，将其加入完美消除序列；
2. 将点 $v$ 与其相邻的边从图上删除；
3. 重复上述过程：
   • 若所有点都被删除，则原图是弦图，且已求得一个完美消除序列；
   • 若剩余图上不存在单纯点，则原图不是弦图。

每次找单纯点需要扫描所有点并检查其邻域是否为团，每轮删除一个点，总时间复杂度 $O(n^4)$。朴素算法正确性显然（由 Lemma 8），但只适合作为理论基准。

3.2 MCS 最大势算法（$O(n+m)$）

最大势算法（Maximum Cardinality Search, MCS）是可以在 $O(n+m)$ 时间内求出无向图完美消除序列的方法（由 Tarjan 与 Yannakakis 于 1984 年提出，见文末参考资料）。

算法流程：

1. 逆序给结点编号：按从 $n$ 到 $1$ 的顺序给点标号（即最后标号的点在完美消除序列最前面）。
2. 设 $label_x$ 表示第 $x$ 个点与多少个已经标号的点相邻；每次选择 $label$ 值最大的未标号结点进行标号。
3. 用链表维护对于每个 $i$，满足 $label_x=i$ 的结点 $x$ 的集合，使得每次取最大 $label$ 与更新 label 都是 $O(1)$。

复杂度分析：由于每条边对 $\sum_{i=1}^n label_i$ 的贡献最多是 $2$（一条边 ${a,b}$ 只会在 $a$、$b$ 中先标号的那个点被计数一次），所有 label 更新总量为 $O(m)$，故总时间复杂度 $O(n+m)$。

正确性证明：

设 $\alpha(x)$ 为 $x$ 在这个序列中的位置。需要证明：对于任何弦图，MCS 求出的序列一定是完美消除序列，即在序列中位于某个点后面且与这个点相连的所有点两两相连。

Lemma 9：考虑三个点 $u,v,w$ 满足 $\alpha(u)<\alpha(v)<\alpha(w)$。如果 $uw$ 相连、$vw$ 不相连，则 $w$ 只给 $u$ 的 $label$ 贡献，不给 $v$ 贡献。为了让 $v$ 比 $u$ 先加入序列，需要存在一个 $x$ 满足 $\alpha(v)<\alpha(x)$ 且 $vx$ 相连、$ux$ 不相连，即 $x$ 只给 $v$ 贡献而不给 $u$ 贡献。

Lemma 10：任意一个弦图一定不存在一个序列 $v_0,v_1,\dots,v_k\ (k\ge 2)$ 满足下列三条性质：

1. $v_iv_j$ 相连当且仅当 $|i-j|=1$（即 $v_0v_1\cdots v_k$ 构成一条诱导路径/无弦路径）；
2. $\alpha(v_0)>\alpha(v_i)\ (i\in[1,k])$；
3. 存在 $i\in[1,k-1]$，满足 $\alpha(v_i)<\alpha(v_{i+1})<\dots<\alpha(v_k)$ 且 $\alpha(v_i)<\alpha(v_{i-1})<\dots<\alpha(v_1)<\alpha(v_k)<\alpha(v_0)$。

证明：由于 $\alpha(v_1)<\alpha(v_k)<\alpha(v_0)$，且 $v_1v_0$ 相连、$v_kv_0$ 不相连，由 Lemma 9 知存在 $x$ 满足 $\alpha(v_k)<\alpha(x)$ 且 $v_kx$ 相连、$v_1x$ 不相连。考虑最小的$j\in(1,k]$ 满足 $v_jx$ 相连，可推出 $v_0x$ 不相连，否则 $v_0v_1\cdots v_jx$ 构成一个长度 $\ge 4$ 且无弦的环，与弦图定义矛盾。若 $\alpha(x)<\alpha(v_0)$，则 $v_0,v_1,\dots,v_j,x$ 也是满足性质的序列；若 $\alpha(v_0)<\alpha(x)$，则 $x,v_j,\dots,v_1,v_0$ 也是满足性质的序列。在上面的推导中我们扩大了 $\min(v_0,v_k)$，于是不断重复这个过程一直推下去，最终一定会产生矛盾。

Theorem 1：对于任何一个弦图，最大势算法求出的序列一定是一个完美消除序列。

证明：考虑任意三个点 $u,v,w$ 满足 $\alpha(u)<\alpha(v)<\alpha(w)$，需要证明若 $uv$ 相连、$uw$ 相连，则 $vw$ 一定相连。反证：假设 $vw$ 不相连，那么 $w,u,v$ 就是一个满足 Lemma 10 中性质的序列（$v_0=w,\ v_1=u,\ v_2=v$ 满足路径、位置与交叉顺序条件），而 Lemma 10 已证明这样的序列在弦图中不存在，矛盾，故 $vw$ 相连。

3.3 MCS 参考代码

以下是 MCS 算法的参考实现（来自 docs/graph/chord.md）。代码中h[i]为 $label=i$ 的结点链表的表头，nxt/lst为链表的前驱后继，p为完美消除序列，rnk为位置数组，tf标记已标号，deg即 $label$ 值，nww为当前非空的最大 label 桶编号：

while (cur) { p[cur] = h[nww]; // 取 label 最大的未标号点 rnk[p[cur]] = cur; // 记录其在序列中的位置 h[nww] = nxt[h[nww]]; // 从链表中删除该点 lst[h[nww]] = 0; lst[p[cur]] = nxt[p[cur]] = 0; tf[p[cur]] = true; // 标记已标号 for (vector<int>::iterator it = G[p[cur]].begin(); it != G[p[cur]].end(); it++) if (!tf[*it]) { // 对未标号的邻居更新 label if (h[deg[*it]] == *it) h[deg[*it]] = nxt[*it]; nxt[lst[*it]] = nxt[*it]; lst[nxt[*it]] = lst[*it]; lst[*it] = nxt[*it] = 0; deg[*it]++; nxt[*it] = h[deg[*it]]; lst[h[deg[*it]]] = *it; h[deg[*it]] = *it; // 移入 label+1 的桶 } cur--; if (h[nww + 1]) nww++; // 维护最大桶编号 while (nww && !h[nww]) nww--; }

重要说明：若原图是弦图，此时求出的就是完美消除序列；但若原图不是弦图，MCS 求出的序列一定不是完美消除序列（否则由 Lemma 8 充分性会推出它是弦图，矛盾）。所以问题转化为：判断求出的序列是否是原图的完美消除序列。

四、判断一个序列是否是完美消除序列

4.1 朴素算法（$O(nm)$）

根据定义，依次判断完美消除序列 $v$ 上，${v_i,v_{i+1},\ldots,v_n}$ 中与 $v_i$ 相邻的点是否构成了一个团。对每个 $v_i$ 枚举其相邻点对并检查边存在性，总时间复杂度 $O(nm)$。

4.2 优化后的算法（$O(n+m)$）

根据完美消除序列的定义，设 $v_i$ 在 ${v_i,v_{i+1},\ldots,v_n}$ 中相邻的点从小到大（按序列位置）为 ${v_{c_1},v_{c_2},\ldots,v_{c_k}}$，则只需判断 $v_{c_1}$（序列位置最靠前的邻居）与其他点是否直接连通即可。这是因为：如果 $v_{c_1}$ 与所有其他邻居都相邻，则整个邻居集合构成团（其他邻居两两相邻可递归由 $v_{c_1}$ 的团性推出——严格地说，只需检查最靠前的邻居连通其余全部邻居）。时间复杂度降为 $O(n+m)$。

参考代码（rnk为位置数组，st为邻接集合）：

jud = true; for (int i = 1; i <= n; i++) { cur = 0; for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++) if (rnk[p[i]] < rnk[*it]) { // 只保留序列中位于其后的邻居 s[++cur] = *it; if (rnk[s[cur]] < rnk[s[1]]) swap(s[1], s[cur]); // s[1] = 最靠前的邻居 } for (int j = 2; j <= cur; j++) if (!st[s[1]].count(s[j])) { // 最靠前邻居必须连通其余全部邻居 jud = false; break; } } if (!jud) printf("Imperfect\n"); else printf("Perfect\n");

至此，弦图判定问题可以在 $O(n+m)$ 的时间复杂度内解决：先跑 MCS 求候选序列，再以 $O(n+m)$ 验证其为完美消除序列。

五、弦图的极大团

5.1 极大团的结构刻画

令 $N(x)$ 表示与 $x$ 直接有边相连且在完美消除序列上位于 $x$ 之后的邻居集合。则弦图的极大团一定为 ${x}+N(x)$。

证明：考虑弦图的一个极大团 $V$，取 $V$ 中点在完美消除序列中第一个出现的点 $x$。$V$ 中其余点都在 $x$ 之后（$x$ 是第一个出现的）且与 $x$ 相邻，所以 $V\subseteq {x}+N(x)$；又因为 $V$ 是极大团，故 $V={x}+N(x)$。

由该刻画立即可得：弦图最多有 $n$ 个极大团（每个点至多对应一个）。

5.2 判定每个 ${x}+N(x)$ 是否为极大团

求出每个 ${x}+N(x)$ 后，需要剔除其中被包含的非极大团：

• 设 $A={x}+N(x),\ B={y}+N(y)$，若 $A\subsetneqq B$，则 $A$ 不是极大团。此时在完美消除序列上显然有 $y$ 在 $x$ 前。
• 设 $nxt_x$ 表示 $N(x)$ 中在完美消除序列上最靠前的点，$y^$ 表示所有满足 $A\subseteq B$ 的 $y$ 中最靠后的点。此时必然有 $nxt_{y^}=x$，否则 $y^$ 不是最靠后的，令 $y^=nxt_{y^*}$ 仍然满足条件。
• $A\subsetneqq B$ 当且仅当 $|A|+1\le |B|$。

于是问题转化为：判断是否存在 $y$，满足 $nxt_y=x$ 且 $|N(x)|+1\le |N(y)|$，总时间复杂度 $O(n+m)$。

参考代码（fst[p[i]]记录 $nxt_{p[i]}$，N[p[i]]$ 记录 $|N(p[i])|$，vis` 标记被包含而非极大团的候选）：

for (int i = 1; i <= n; i++) { cur = 0; for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++) if (rnk[p[i]] < rnk[*it]) { s[++cur] = *it; if (rnk[s[cur]] < rnk[s[1]]) swap(s[1], s[cur]); } fst[p[i]] = s[1]; // N(x) 中序列位置最靠前的点 N[p[i]] = cur; // |N(x)| } for (int i = 1; i <= n; i++) { if (!vis[p[i]]) ans++; // 未被标记的点对应一个极大团 if (N[p[i]] >= N[fst[p[i]]] + 1) vis[fst[p[i]]] = true; // {x}+N(x) 被包含则标记 }

注意处理s[1]为空的边界（$N(x)$ 为空集时 ${x}+N(x)={x}$ 即单点团）。

六、弦图的色数与团数

在一般图上，最小染色是 NP-Hard 的；但在弦图上，借助完美消除序列可以贪心求解。

构造方法：按完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小颜色（即与所有已染色的邻居都不冲突的最小颜色编号）。时间复杂度 $O(m+n)$。

正确性证明：设以上方法使用了 $t$ 种颜色，则 $t\ge \chi(G)$（任何合法染色都至少需要 $\chi$ 种颜色）。另一方面，从后往前染色时，每当引入一种新颜色，被染的这个点与其所有"序列位置在其后且已染色"的邻居都相邻，且它们两两相邻（完美消除序列性质），共同构成一个团，故 $t\le \omega(G)$，即 $t=\omega(G)$。由 Lemma 1 得 $t=\omega(G)\le \chi(G)$。综上 $t=\chi(G)=\omega(G)$，即弦图色数等于团数，贪心染色达到最优。

只需数值不求方案：当无需具体染色方案、只需求弦图的色数/团数时，可以直接取 $|{x}+N(x)|$ 的最大值（即最大团的点数），一行代码即可：

for (int i = 1; i <= n; i++) ans = max(ans, deg[i] + 1);

这里deg[i]若为完美消除序列中位于 $i$ 之后的邻居数 $|N(i)|$，则deg[i]+1 = |{i}+N(i)|$恰为包含 $i$ 的那个团的规模。

七、弦图的最大独立集与最小团覆盖

同样在一般图上 NP-Hard 的两个问题，在弦图上也有线性贪心解法。

最大独立集：按完美消除序列从前往后扫描，选择所有没有与已经选择的点有直接连边的点。

最小团覆盖：设上面求出的最大独立集为 ${v_1,v_2,\ldots,v_t}$，则团的集合 ${{v_1+N(v_1)},{v_2+N(v_2)},\ldots,{v_t+N(v_t)}}$ 为图的最小团覆盖。两者时间复杂度均为 $O(n+m)$。

正确性证明：设以上方案得到的独立集大小与团覆盖数为 $t$。贪心选择的点集中任意两点不相邻，故 $t\le \alpha(G)$；而每个团 ${v_i+N(v_i)}$ 覆盖了 $v_i$ 且这些团覆盖全体点，故 $t\ge \kappa(G)$。由 Lemma 2 得 $\alpha(G)\le \kappa(G)$，所以 $t=\alpha(G)=\kappa(G)$，即最大独立集等于最小团覆盖数，且贪心同时达到两者最优。

参考代码（vis在此处标记"已被已选独立集点覆盖/相邻"的点）：

for (int i = 1; i <= n; i++) if (!vis[p[i]]) { // 按序列从前往后，未被覆盖则选入独立集 ans++; for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++) vis[*it] = true; // 其邻居不能入选独立集 }

八、弦图五大问题复杂度一览

从表中可以清晰看到弦图的价值：四个经典 NP-Hard 参数在弦图上全部退化为线性可解，且核心算法共用同一个完美消除序列，一套预处理（MCS）即可支撑全部问题。

九、实战指引与进一步阅读

• 应用场景：弦图理论在区间图（interval graph）染色、完美图（perfect graph）理论、超图无环性检验、稀疏线性方程组消元顺序（消元时保持图性质）等领域都有直接应用；竞赛中常见模型是"区间相交图"类问题，其本质即为弦图。
• 代码落地：完整参考代码均出自 docs/graph/chord.md，实现时注意 MCS 的链表桶结构、逆序标号约定，以及验证阶段只检查"最靠前邻居连通其余邻居"这一线性技巧。
• 相关主题：团与最大团的一般性算法见 docs/graph/max-clique.md（Bron–Kerbosch 算法），基础术语见 docs/graph/concept.md；图染色专题可继续阅读 docs/graph/color.md。

习题

• SPOJ FISHNET - Fishing Net（弦图判定模板题）
• P3196 [HNOI2008] 神奇的国度（弦图染色/团数应用）
• P3852 [TJOI2007] 小朋友（弦图相关综合应用）

参考资料

• yhx-12243 的 OI-transit 笔记《弦图相关》
• 2009 WC 讲稿《弦图与区间图》（陈丹琦）
• 租酥雨《弦图总结》系列博客
• R. E. Tarjan and M. Yannakakis,Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.（MCS 算法的原始出处）

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki