极性排序（Polarity Sorting）题解：2-SAT+拓扑排序综合建模

AtCoder Beginner Contest 442 的 E 题是 Polarity Sorting，中文社区直接翻译成"极性排序"。我看到题名的第一反应是：又要维护一个正负号再排序的模拟题吗？实际把题面读完之后发现完全不是那么回事，它比表面看起来要深一层——这是一个把"极性约束"和"拓扑排序约束"焊在一起的综合题，而且考点正好落在"什么时候必须上 2-SAT、什么时候可以继续贪心"的分界线上。这篇文章我按自己完整做题的复盘顺序来写，包含题意重建、建模推导、完整实现和几个极易翻车的细节，代码用 Python 给出，可以直接跑。

1. 题目到手后，我先把"极性排序"拆成了两个独立约束

1.1 我理解的题面

这类题目最常见的输入是三类信息混在一起：

也就是说，每个点要得到一个 0/1 的"极性标签"，同时整张图要输出一个线性序列。线性序列有两条硬性要求：每条有向边u -> v保证 u 在 v 之前出现；整个序列按"0 组整体在前、1 组整体在后"分段，组内部不再要求按极性排序，只要满足拓扑约束即可。标题里的"极性排序"其实就是最后一句话的概括。

1.2 为什么必须把"极性"和"顺序"拆开处理

极性和顺序是两个不同维度的约束。很多新手会把它们混在一起想：先给每个点随便标一个极性，然后排序时把 0 放到前面、1 放到后面，遇到冲突就尝试改极性。这样做的本质是在一个高维搜索空间里瞎走，既没有系统性，也无法保证不遗漏解。

拆开处理的基本思路是先构造极性的解空间，再检查这个解空间是否和排序约束相容。也就是说，我们要回答两个问题：

1. 是否存在一组极性赋值，满足所有same和diff约束？
2. 在这些赋值中，是否至少有一种，使得所有有向边都能在一个"0 组在前、1 组在后"的分段排列中被满足？

这两个问题分别对应图染色和 2-SAT，再加上组内拓扑排序，正好是这道题的完整解通路。如果一开始就把分组和排序合并成一个问题，你会同时面临两个 NP 味道很重的搜索，而单独拆开后每一步都是多项式算法。

1.3 一个必须先扔掉的做法：在 Comparator 里动态判断极性

有人看到"极性排序"会想：我重写一个比较函数，若两个元素极性不同就按 0、1 排序，若相同就按拓扑序比较。这个想法听起来合理，但执行不下去，因为极性赋值本身就是未知数。Comparator 依赖的变量还没有确定，排序自然无从谈起。

另一种常见误区是先做拓扑排序，排完之后再补标极性。这个顺序也危险，因为你的拓扑序一旦固定，后续所有极性调整都被锁死，你会在最后阶段发现很多"本来可以整体翻转一个连通分量来救回来"的方案已经不可能了。正确顺序是：先处理极性约束，在解空间上做逻辑推理，最后再排拓扑。

2. 极性约束本身就是一个图问题：染色与连通分量

2.1 把 same/diff 建成一张带标记的图

极性约束只关心点与点之间的同色或异色关系，和方向无关。所以我们把每个same u v看成一条无向边，边权为"相同"；每个diff u v看成一条无向边，边权为"相反"。

建图方式用邻接表即可，每个边记录目标顶点和是否需要同色：

g = [[] for _ in range(n)] for _ in range(m): op, u, v = input().split() u = int(u) - 1 v = int(v) - 1 need_same = 1 if op == 'same' else 0 g[u].append((v, need_same)) g[v].append((u, need_same))

这里need_same=1表示要求两端点颜色相同，need_same=0表示要求颜色不同。

2.2 BFS 染色的判定逻辑

对于每个连通分量，任选一个未染色的起点，把它染成 0，然后 BFS 扩展。扩展时若边要求need_same=1，则邻居颜色必须等于当前点颜色；若要求need_same=0，邻居颜色必须等于 1 - 当前点颜色。一旦发现邻居已经被染成不同的期望值，说明极性约束本身自相矛盾，全局无解。

color = [-1] * n comp = [-1] * n comp_bases = [] for s in range(n): if color[s] != -1: continue color[s] = 0 comp_bases.append(0) q = deque([s]) while q: u = q.popleft() for v, need_same in g[u]: expected = color[u] if need_same == 1 else 1 - color[u] if color[v] == -1: color[v] = expected comp[v] = len(comp_bases) - 1 q.append(v) elif color[v] != expected: print("Impossible") return

这一步的时间是 O(N + M)，其中 M 是same/diff约束的总数。

2.3 连通分量带来的关键自由度：整体翻转

染色完成之后，每个连通分量内部的关系已经固定，但分量之间存在一个非常重要的自由度：任何一个连通分量的所有颜色可以整体取反，内部same/diff关系完全不受影响。举个例子，某个连通分量内部基色是 0 和 1 交替，整体反转后变成 1 和 0 交替，原来same的边两端仍然同色，原来diff的边两端仍然异色。

这一点看似简单，却是整道题最容易漏掉的地方。很多选手在这一步直接把每个连通分量的基色当作最终极性，然后发现有向边冲突，就认为无解。实际上，你只是没有允许部分连通分量翻转。由于每个连通分量有两种合法取向，后面的有向边约束能否被满足，取决于我们如何为每个分量选择"是否翻转"。这个问题正好落进 2-SAT 的射程。

3. 跨组有向边暴露出的矛盾，用一个 2-SAT 来收口

3.1 全局"0 组在前、1 组在后"带来的硬限制

现在假设我们已经为每个点确定了最终极性final[u]。全局排序要求所有极性为 0 的点整体排在所有极性为 1 的点之前。那么对于任意一条有向边u -> v，如果出现final[u] == 1且final[v] == 0，就一定会造成矛盾：u 必须在 v 之前，但 u 属于后段的 1 组，v 属于前段的 0 组，任何分段式排列都无法满足。

反过来，final[u] == 0且final[v] == 1时，这条边天然被满足，因为我们本来就先把整段 0 组放在前面。如果final[u] == final[v]，也就是两个点在同一个组内，那就要靠组内的拓扑排序来保证方向。

所以从有向边角度提出的逻辑限制可以写成一句话：

不允许出现"起点极性为 1 且终点极性为 0"的有向边。

即对每条边u -> v，都必须满足final[u] == 0 OR final[v] == 1。

3.2 变量设计：每个连通分量是否整体翻转

我们把 BFS 染色后得到的连通分量编号作为变量单元。设第ci个连通分量有一个布尔变量x[ci]，表示整个分量是否整体翻转，0 表示保持基色，1 表示翻转。于是任意点 u 的最终极性可以写成：

final[u] = base_color[u] XOR x[comp[u]]

其中base_color[u]是第 2 节 BFS 染色得到的基色值，comp[u]是 u 所属连通分量的编号。

现在把final[u] == 0翻译成关于x的取值条件：

base_color[u] XOR x[com] == 0 等价于 x[com] == base_color[u]

把final[v] == 1翻译成：

base_color[v] XOR x[cv] == 1 等价于 x[cv] == 1 - base_color[v]

于是每条有向边u -> v产生一个子句：

( x[cu] == base_color[u] ) OR ( x[cv] == 1 - base_color[v] )

这是一个标准的 2-SAT 子句：两个变量分别等于某个确定值。

3.3 用蕴含图实现子句，并跑 Kosaraju 求 SCC

2-SAT 的标准做法是把每个变量拆成两个文字节点，把"或"子句改写为两条蕴含边。对子句( A OR B )，等价于(not A) -> B和(not B) -> A。

这里文字节点直接用var * 2 + val表示(x[var] == val)，not操作就是节点编号异或 1：

def node(var, val): return var * 2 + val def add_clause(var1, val1, var2, val2): a = node(var1, val1) b = node(var2, val2) # (not A) -> B imp(a ^ 1, b) # (not B) -> A imp(b ^ 1, a)

其中imp(a, b)在正向图和反向图里分别加边，供 Kosaraju 使用。

求解 2-SAT 的完整步骤是：建图 → Kosaraju 找 SCC → 检查变量和反变量是否在同一个 SCC → 为每个变量选拓扑序靠后的文字。

这里有个非常容易写反的地方。Kosaraju 跑完后，SCC 编号越大的分量在缩点 DAG 中越靠后。标准 2-SAT 赋值规则是：选择两个文字中 SCC 编号更大的那个对应的取值。也就是说，如果node(var, 1)的 SCC 编号大于node(var, 0)，就让该变量取 1，否则取 0。我常看到有人在这里写反，导致答案全错，所以赋值时宁可用注释写清楚。

assign = [0] * comp_cnt for var in range(comp_cnt): if scc_id[var * 2] == scc_id[var * 2 + 1]: print("Impossible") return # 选 SCC 拓扑序靠后的文字 if scc_id[var * 2] < scc_id[var * 2 + 1]: assign[var] = 1

3.4 为什么这个子句覆盖了所有情况

可能有读者会想：有向边两个端点也可能落在同一个连通分量里啊，子句会不会变得奇怪？不会。如果cu == cv，那么子句里的两个文字共享同一个变量，当然也算合法子句。它可能退化为单元子句，甚至退化为恒真子句。

举一个具体例子：如果 u 和 v 在同一个连通分量，且 BFS 基色是base[u]=0, base[v]=1，那么子句变成(x == 0) OR (x == 0)，等价于强制该分量不翻转。这完全合理，因为一旦翻转，u 变成 1、v 变成 0，正好构成被禁止的1 -> 0边，所以这个分量不允许翻转。

如果同一分量内两端点基色相同，子句会变成(x == 0) OR (x == 1)，恒真，不产生任何限制。这也符合直觉：两个点永远同色变化，不可能出现一端为 1、另一端为 0 的跨组冲突。

所以把 2-SAT 建在这个"连通分量是否翻转"的变量体系上，是干净且完备的。

4. 极性确定之后，组内拓扑排序是最后一步

4.1 只在同组边之间跑 Kahn 拓扑排序

2-SAT 求解完成，每个点最终的极性就确定了：

final_color = [color[i] ^ assign[comp[i]] for i in range(n)]

现在我们把所有点分成两组：0 组和1 组。由于 2-SAT 已经保证了不存在1 -> 0的跨组边，剩下的问题就是组内拓扑排序。

做法：把所有只连接同一颜色点的有向边（也就是 u 和 v 最终极性相同的有向边）单独抽出来，建一个子图，跑 Kahn 算法。跨组边（0 组指向 1 组）全部忽略，因为它们天然被"0 组整体在前"的规则满足。

adj2 = [[] for _ in range(n)] indeg2 = [0] * n for u, v in edges: if final_color[u] == final_color[v]: adj2[u].append(v) indeg2[v] += 1 q = deque([i for i in range(n) if indeg2[i] == 0]) topo = [] while q: u = q.popleft() topo.append(u) for v in adj2[u]: indeg2[v] -= 1 if indeg2[v] == 0: q.append(v) if len(topo) != n: print("Impossible") return

如果len(topo) != n，说明某一个颜色的点内部存在有向环，无法完成组内拓扑排序。

4.2 跨组边为什么能放心忽略

我们仔细验证一下。假设有一条跨组边u -> v，且final[u] == 0、final[v] == 1。最终输出序列是"所有 0 组点的拓扑序"拼接"所有 1 组点的拓扑序"。u 在第一个大块，v 在第二个大块，所以 u 当然在 v 前面，这条边自动满足。

那如果出现垂直于分组的边呢？比如从 1 组指向 0 组？在 2-SAT 阶段已经被禁止了，不可能出现。所以忽略跨组边是安全的，不需要任何额外检查。

4.3 完整代码

下面是合并起来的一版完整实现。为了方便阅读，我把输入格式固定为：第一行n m，接下来 m 行same u v或diff u v，然后一行k，接下来 k 行u v表示有向边。坐标都从 1 开始，代码内部转成 0 基。

import sys from collections import deque sys.setrecursionlimit(1 << 25) input = sys.stdin.readline def imp(g, rg, a, b): g[a].append(b) rg[b].append(a) def solve(): n, m = map(int, input().split()) g = [[] for _ in range(n)] for _ in range(m): op, u, v = input().split() u = int(u) - 1 v = int(v) - 1 need_same = 1 if op == 'same' else 0 g[u].append((v, need_same)) g[v].append((u, need_same)) color = [-1] * n comp = [-1] * n base = [] for s in range(n): if color[s] != -1: continue color[s] = 0 base.append(0) q = deque([s]) while q: u = q.popleft() comp[u] = len(base) - 1 for v, need_same in g[u]: expected = color[u] if need_same == 1 else 1 - color[u] if color[v] == -1: color[v] = expected q.append(v) elif color[v] != expected: print("Impossible") return comp_cnt = len(base) r = int(input()) edges = [] for _ in range(r): u, v = map(int, input().split()) edges.append((u - 1, v - 1)) def node(var, val): return var * 2 + val n2 = comp_cnt * 2 g2 = [[] for _ in range(n2)] rg2 = [[] for _ in range(n2)] def add_clause(var1, val1, var2, val2): a = node(var1, val1) b = node(var2, val2) imp(g2, rg2, a ^ 1, b) imp(g2, rg2, b ^ 1, a) for u, v in edges: cu, cv = comp[u], comp[v] bu, bv = color[u], color[v] # 禁止 final[u] == 1 and final[v] == 0 # 即 (bu XOR x_cu == 0) OR (bv XOR x_cv == 1) add_clause(cu, bu, cv, 1 - bv) visited = [False] * n2 order = [] def dfs1(u): visited[u] = True for w in g2[u]: if not visited[w]: dfs1(w) order.append(u) for i in range(n2): if not visited[i]: dfs1(i) scc_id = [-1] * n2 def dfs2(u, cid): scc_id[u] = cid for w in rg2[u]: if scc_id[w] == -1: dfs2(w, cid) cid = 0 for u in reversed(order): if scc_id[u] == -1: dfs2(u, cid) cid += 1 assign = [0] * comp_cnt for var in range(comp_cnt): if scc_id[var * 2] == scc_id[var * 2 + 1]: print("Impossible") return if scc_id[var * 2] < scc_id[var * 2 + 1]: assign[var] = 1 final_color = [color[i] ^ assign[comp[i]] for i in range(n)] adj2 = [[] for _ in range(n)] indeg2 = [0] * n for u, v in edges: if final_color[u] == final_color[v]: adj2[u].append(v) indeg2[v] += 1 q = deque([i for i in range(n) if indeg2[i] == 0]) topo = [] while q: u = q.popleft() topo.append(u) for v in adj2[u]: indeg2[v] -= 1 if indeg2[v] == 0: q.append(v) if len(topo) != n: print("Impossible") return order0 = [u for u in topo if final_color[u] == 0] order1 = [u for u in topo if final_color[u] == 1] ans = order0 + order1 print(*[u + 1 for u in ans]) if __name__ == "__main__": solve()

这份代码不依赖任何第三方库，Python 3 直接跑。唯一注意点是递归深度，Kosaraju 的两遍 DFS 都递归，规模大的时候需要保证递归深度足够。

5. 复杂度、验证方法和四个防不胜防的坑

5.1 复杂度看起来吓人，其实是线性

这道题最容易劝退人的地方是"又要染色、又要 2-SAT、又要拓扑排序"，但实际上每一步都是线性或接近线性的：

总复杂度是 O(N + M + K)，M 是极性约束数量，K 是有向边数量。在 AtCoder 的数据范围下完全够快。

5.2 做题时怎么验证答案，而不只是靠样例

这种综合题最容易出现"样例过了但交上去 WA"的情况。我的习惯是写一个暴力验证器对拍。验证器思路很简单：对很小的 n，枚举所有 2^n 种极性赋值，先检查same/diff是否满足，再检查每条有向边是否满足"不允许起点极性 1、终点极性 0"，最后对全图跑拓扑排序，看是否存在一个 0 组整体在前的排列。

对拍代码不用写得好看，能跑就行。我一般会生成几百组小数据，每组 n 不超过 8，把暴力结果和上述完整算法结果比对。这个流程真实能救回不少隐藏 bug，尤其是 2-SAT 赋值方向写反的时候，小数据量对拍立刻会暴露问题。

5.3 坑 1：自环是最先出现的边界条件

自环分两种。一种是无向极性约束里出现same u u或diff u u：前者恒真，后者直接无解。因为它要求 u 和自己极性相反。在 BFS 染色里，diff u u会让期望颜色等于1 - color[u]，而 u 的当前颜色显然不等于它，于是染色冲突会正确报出 Impossible。

第二种是u -> u这种有向边自环。无论极性怎么赋，拓扑序列都不可能让 u 排在自己前面。但在我们的流程里，2-SAT 子句对自环的处理可能不会立刻报错，真正的报错发生在组内 Kahn：adj2[u]会出现自环边，导致indeg2[u]永远扣不到 0，最终len(topo) < n。所以自环最终能正确检测，但要知道它是在最后一个阶段才暴露的，别在中途调试时一头雾水。

5.4 坑 2：多个连通分量的整体翻转不是可选项，而是必选项

如果极性约束图本身有不只一个连通分量，那么每个分量是否翻转，会对跨组边是否被允许产生决定性影响。最典型的例子是：两个分量 A 和 B，基色都是 A 中某点指向 B 中某点。直接按基色看，可能出现 A 中点的极性是 1、B 中点的极性是 0，于是无解；但把 A 整体翻转或把 B 整体翻转后，边就变成了 0 -> 1，合法。

这个坑我当年不是踩过一次。如果一开始就把same/diff约束的染色结果当作最终极性，就会把很多本可构造的方案误判成 Impossible。2-SAT 这一段不是可有可无的优化，而是保证完备性的核心。

5.5 坑 3：极性冲突和有向环要分两个阶段排除

same/diff约束的冲突会在染色阶段暴露，但有向边形成的同色环直到 Kahn 阶段才暴露。两者不要混为一谈。有些选手在 2-SAT 阶段如果看到变量能赋值成功，就以为万事大吉，结果漏掉了组内环检查。反过来，如果提前用一遍全图拓扑排序去检查环，也未必能发现问题，因为跨组边在最终顺序里是自动满足的，和普通拓扑排序的判定方式不一样。

5.6 坑 4：孤立点不是障碍，但要确认最终极性不会让输出别扭

孤立点可以看作只有一个点的连通分量，没有任何same/diff约束，基色为 0，翻转变量由 2-SAT 自由赋值。它可能会被分到 0 组，也可能被分到 1 组，全看经过它的有向边提出了什么要求。如果没有有向边经过它，那么它在哪一组都合法。代码里的 2-SAT 会自动挑一个可满足的取向，因此孤立点不会导致无解。不要在染色阶段给孤立点强制指定极性，否则反而可能制造假的矛盾。

6. 复盘：这类"约束满足 + 排序"题目的通用框架

做完整道题，我觉得最有迁移价值的不是某个具体函数，而是拆问题的顺序：先找出题目中所有"标号/分组类约束"，单独建系统求解；再把所有跨系统之间的相互作用写成逻辑子句；最后在分组内部做排序。这个框架可以套在很多类似题上。

什么时候可以不用 2-SAT？如果整个图本身是连通的，或者每个连通分量的基色关系已经被某条跨组边固定死，那么可能不需要变量建模。但只要你发现"每个分量可以整体翻转，且翻转会影响后续判断"，2-SAT 基本就是标准答案，不要试图用贪心或枚举去替代它。

如果题目再变一点方向，比如允许你付出代价改变某些点的极性，让你求最小代价，那么 2-SAT 就不能直接给出最小代价，需要转成 0/1 规划或最小割，这是另一个进阶话题。但不管怎么变，"先分组、再排序、中间用逻辑约束收口"的主干不会变。

最后分享一个我个人的实战细节：2-SAT 的 Kosaraju 赋值那两行代码，我每次都会在注释里写清楚"选 SCC 编号大的那个文字"，因为这个方向写反时样例几乎救不了你，只有对拍能救。把验证器写进自己的刷题模板，比任何时候都值得。