「一本通 3.5 练习 5」和平委员会

形式化题目

有 $n$ 个党派，每个党派恰有 $2$ 名代表，编号为 $2i-1$ 和 $2i$ 。需要从中选出 $n$ 名代表成立委员会，满足：

每个党派必须且恰好选出 $1$ 名代表。
有 $m$ 对代表互相厌恶，不能同时入选。

求任意一种合法的选择方案，将选出的 $n$ 个代表编号按升序排列，每行输出一个。如果无法成立，输出 NIE。数据范围： $1 \le n \le 8000$ ， $0 \le m \le 20000$ 。

正解

思路

本题为标准 2-SAT 模型。党派 $i$ 必须在代表 $2i-1$ 和 $2i$ 中二选一。若两名代表 $a$ 和 $b$ 互相厌恶，表示“选 $a$ 则必须不选 $b$ （即必须选 $b$ 的同党伙伴）”，以及“选 $b$ 则必须不选 $a$ （必须选 $a$ 的同党伙伴）”。据此，我们在图中连两条有向边 $a \to b'$ 与 $b \to a'$ ，共 $2n$ 个节点。

建图后，使用 Tarjan 算法求强连通分量（SCC）：

若同党的 $2i-1$ 和 $2i$ 在同一 SCC 内，则产生逻辑矛盾，直接判定无解，输出 NIE。
否则，Tarjan 算法求出的 SCC 编号天然为其缩点图 DAG 的逆拓扑序。对每对同党代表，选取 SCC 编号较小的一方即可满足所有蕴含条件。按 $1 \dots n$ 的顺序输出所选节点，自然符合题目的升序要求。

为防止深度过大导致爆栈，Tarjan 算法需使用迭代版实现。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 08:30
# update_at: 2026-10-09 08:48

import sys
from collections.abc import Iterator

type AdjList = tuple[list[int], list[int], list[int]]  # 链式前向星三元组 (head, to_edge, nxt)


def partner(x: int) -> int:
    """代表 x 的同党伙伴：奇数 2i-1 配偶数 2i，偶数 2i 配奇数 2i-1。"""
    return x + 1 if x % 2 else x - 1


def build_graph(n: int, m: int, data: Iterator[int]) -> AdjList:
    """读入 m 个厌恶对并建 2-SAT 蕴含图，返回链式前向星的 (head, to_edge, nxt)。

    厌恶对 (u, v) 表示 u、v 不能同时入选；由于每党恰选 1 人，「不选 v」等价于
    「选 v 的同党伙伴 partner(v)」，于是有两条蕴含边 u -> partner(v)、v -> partner(u)。
    u == v 时边为 u -> partner(u)，正好表达「u 不能入选」，无需特判。
    """
    head = [0] * (2 * n + 1)     # head[u] 是 u 的第一条出边编号
    to_edge = [0] * (2 * m + 1)  # to_edge[e] 是第 e 条边的终点
    nxt = [0] * (2 * m + 1)      # nxt[e] 是同起点的下一条边编号
    edge_cnt = 0
    for _ in range(m):
        u, v = next(data), next(data)
        for start, end in ((u, partner(v)), (v, partner(u))):
            edge_cnt += 1
            to_edge[edge_cnt] = end
            nxt[edge_cnt] = head[start]
            head[start] = edge_cnt
    return head, to_edge, nxt


def tarjan_scc(size: int, head: list[int], to_edge: list[int],
               nxt: list[int]) -> list[int]:
    """迭代版 Tarjan 求强连通分量，返回每个结点（1..size-1）的 SCC 编号。

    编号按结点完成顺序递增，恰好是缩点 DAG 拓扑序的**逆序**。
    写成显式栈是因为数据里最长蕴含链达 16000 层（spo8/spo12 实测 15999），
    递归会爆栈，而 Python 默认递归上限只有 1000。
    """
    dfn = [0] * size        # Tarjan 时间戳，0 表示还没访问过
    low = [0] * size        # 所在 SCC 能回溯到的最小 dfn
    scc = [0] * size        # 结点所属的 SCC 编号
    in_st = [False] * size  # 结点当前是否还在 SCC 栈里
    edge_ptr = [0] * size   # 每个结点扫描到哪条出边（对应递归里的 for 游标）
    timer = scc_cnt = 0
    st: list[int] = []       # SCC 栈
    call_st: list[int] = []  # 手工调用栈，模拟递归的调用链

    for root in range(1, size):
        if dfn[root]:
            continue
        timer += 1
        dfn[root] = low[root] = timer
        st.append(root)
        in_st[root] = True
        edge_ptr[root] = head[root]
        call_st.append(root)

        while call_st:
            u = call_st[-1]
            e = edge_ptr[u]

            if e:  # 还有出边没扫完，继续深入
                edge_ptr[u] = nxt[e]
                v = to_edge[e]
                if not dfn[v]:
                    timer += 1
                    dfn[v] = low[v] = timer
                    st.append(v)
                    in_st[v] = True
                    edge_ptr[v] = head[v]
                    call_st.append(v)
                elif in_st[v] and dfn[v] < low[u]:
                    low[u] = dfn[v]  # 回边指向栈内结点，用它更新追溯值
            else:  # 出边扫完，回溯
                if low[u] == dfn[u]:
                    scc_cnt += 1
                    while True:
                        v = st.pop()
                        in_st[v] = False
                        scc[v] = scc_cnt
                        if v == u:
                            break
                call_st.pop()
                if call_st and low[u] < low[call_st[-1]]:
                    low[call_st[-1]] = low[u]

    return scc


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)  # 缺输入保护：一个 token 都没有就直接返回
    if n is None:
        return
    m = next(data, 0)

    head, to_edge, nxt = build_graph(n, m, data)
    scc = tarjan_scc(2 * n + 1, head, to_edge, nxt)

    # 同党两名代表落在同一个 SCC ⇒ 选一个必然推出另一个，与「每党恰 1 人」矛盾。
    if any(scc[2 * i - 1] == scc[2 * i] for i in range(1, n + 1)):
        print("NIE")
        return

    # SCC 编号越小越靠近缩点 DAG 的汇点，选它不会推出矛盾；
    # 按党派递增输出，天然满足题面的升序要求。
    committee = [2 * i - 1 if scc[2 * i - 1] < scc[2 * i] else 2 * i
                 for i in range(1, n + 1)]
    if committee:
        print('\n'.join(map(str, committee)))


if __name__ == '__main__':
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 08:30
 * update_at: 2026-10-09 08:48
 */
// main.cpp：2-SAT。每党恰选 1 人 + 互相厌恶者不能同选。
// 用迭代版 Tarjan 求 SCC，避免 n=8000 的长链上递归爆栈（数据里最深链 16000 层）。
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXV = 16005; // 2 * 8000 + 余量：每个代表是 2-SAT 图上的一个结点
const int MAXE = 40005; // 2 * 20000 + 余量：每个厌恶对贡献两条蕴含边

int head[MAXV];    // 链式前向星：结点 u 的第一条出边编号
int to_edge[MAXE]; // 第 i 条边指向的结点编号
int nxt[MAXE];     // 第 i 条边的下一条兄弟边编号
int edge_cnt;      // 已加入的边数

int dfn[MAXV]; // Tarjan 时间戳，0 表示结点还没被访问过
int low[MAXV]; // Tarjan 追溯值：所在 SCC 能回溯到的最小 dfn
int scc[MAXV]; // 结点所属强连通分量编号（按完成序编号，天然是缩点 DAG 拓扑序的逆序）
int timer;     // dfn / low 的计数器
int scc_cnt;   // 已经求出的 SCC 个数

int st[MAXV];      // Tarjan 的 SCC 栈
int top;           // SCC 栈顶下标
bool in_st[MAXV];  // 结点当前是否还在 SCC 栈里

int call_st[MAXV]; // 迭代版 Tarjan 的手工调用栈，模拟递归的调用链
int call_top;      // 手工调用栈顶下标
int edge_ptr[MAXV]; // 每个结点正在扫描的出边游标，模拟递归里 for 循环的位置

// 加一条 u -> v 的蕴含边。
void add_edge(int u, int v) {
    to_edge[++edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 代表 x 的同党伙伴：奇数 2i-1 配偶数 2i，异或 1 即可互换。
int get_other(int x) {
    return (x % 2 == 1) ? (x + 1) : (x - 1);
}

// 迭代版 Tarjan：从 root 出发求强连通分量，写成显式栈是为了不受递归深度限制。
void tarjan(int root) {
    call_st[++call_top] = root;
    dfn[root] = low[root] = ++timer;
    st[++top] = root;
    in_st[root] = true;
    edge_ptr[root] = head[root];

    while (call_top > 0) {
        int u = call_st[call_top];
        int e = edge_ptr[u];

        if (e) { // 还有出边没扫完，继续往下走
            edge_ptr[u] = nxt[e];
            int v = to_edge[e];
            if (!dfn[v]) {
                dfn[v] = low[v] = ++timer;
                st[++top] = v;
                in_st[v] = true;
                edge_ptr[v] = head[v];
                call_st[++call_top] = v;
            } else if (in_st[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        } else { // 出边扫完，回溯
            if (low[u] == dfn[u]) {
                ++scc_cnt;
                while (true) {
                    int v = st[top--];
                    in_st[v] = false;
                    scc[v] = scc_cnt;
                    if (u == v) break;
                }
            }
            --call_top;
            if (call_top > 0) {
                int p = call_st[call_top];
                low[p] = min(low[p], low[u]);
            }
        }
    }
}

void solve() {
    int n, m;
    if (!(cin >> n >> m)) return;

    // 厌恶对 (u,v)：不能同时入选。由于每党恰选 1 人，
    // 「不选 v」等价于「选 v 的同党伙伴 get_other(v)」，于是
    //   u -> get_other(v)   且   v -> get_other(u)
    // 当 u == v 时连边 u -> get_other(u)，正好表达「u 不能入选」，无需特判。
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, get_other(v));
        add_edge(v, get_other(u));
    }

    for (int i = 1; i <= 2 * n; ++i) {
        if (!dfn[i]) tarjan(i);
    }

    // 同党两名代表落在同一个 SCC ⇒ 选一个就必然推出另一个，与「每党恰 1 人」矛盾。
    for (int i = 1; i <= n; ++i) {
        if (scc[2 * i - 1] == scc[2 * i]) {
            cout << "NIE\n";
            return;
        }
    }

    // Tarjan 的 SCC 编号是拓扑序的逆序：编号小的在拓扑序上更靠后（更靠近汇点），
    // 选它不会推出矛盾。按 i 从小到大输出，天然就是升序。
    for (int i = 1; i <= n; ++i) {
        if (scc[2 * i - 1] < scc[2 * i]) {
            cout << 2 * i - 1 << "\n";
        } else {
            cout << 2 * i << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度： $O(n + m)$ 。 $2n$ 个节点与 $2m$ 条有向边，Tarjan 算法线性遍历图。
空间复杂度： $O(n + m)$ 。存储图结构及栈、强连通分量数组。

总结

算法与复杂度：本题采用 2-SAT + SCC（迭代版 Tarjan）解法，总时间复杂度为 $O(n + m)$ 。
数据缺陷第 19 类（期望输出本身非法）：spo13.out 是一个非法解，并非多解。该输出包含 3907 对互相厌恶的冲突（随机选择的期望冲突数为 $m/4 \approx 4000$ ），且输出了高达 15999 的编号，而 spo13.in 的输入值域仅到 7999（8000 个党中 4014 个无约束）。经过对错位、偏移、重标号等各种错配假设的穷举排除，确认该 .out 本质与随机生成的序列无异。
区分「程序错 / 多解 / .out 非法」的方法论：判据 {ours[i], theirs[i]} == {2i-1, 2i} 鉴别力为 0（对任意两个满足“升序+每党恰 1 名”的集合恒为 True）。要正确判定多解问题，必须独立验证解的合法性（统计厌恶对冲突数），不能通过单纯比较解的形态得出结论。
SPJ 的判据与验证：SPJ 建模正确且极具分辨力。异源测试中，不建图的 DPLL 算法与 Kosaraju 在 4000 组随机+3016组穷举中 0 分歧。针对 NIE 测试点输出的 BFS 可达性证书验证均准确（显式找出了 $v \to \neg v$ 与 $\neg v \to v$ 两条通路）；对照组注入的 8 种非法委员会全被拒绝（包含厌恶同选），4 种合法解全被接受；此外，它也正确地独立拒绝了前述非法的 spo13.out。
CRLF 缺陷：所有 14 个 .in 与 .out 文件的行尾均为 \r\n（CRLF）。虽然程序正常输出形如 NIE\n 或末尾带 \n，但在字节级对比上由于数据缺陷导致 check_bytes 判定为 0/14 失败，需由 SPJ 接管。
递归 vs 迭代 Tarjan：图成链时最大递归深度可达 15999（如 spo8）。实测发现递归版 Tarjan 在栈空间 1MB~1.4MB 时必定段错误崩溃（MinGW/Windows 默认栈恰为 1MB），需要 8MB 默认栈方有余量。因此迭代版 Tarjan 算法是非常必要且正确的实现。

V1 反事实表与策略分辨力：

变体	改动	失败点数
A	判 SCC 时把 `==` 改成 `!=`	11/14
B	赋值规则取反（选 scc 大的）	10/14
B2	降序输出（换循环方向）	11/14
B3	选更大的 scc 编号	10/14
W	反转 scc 编号再选	10/14
C	蕴含边方向反过来	10/14
D	总是选 `2i-1`	10/14
spj 关掉	临时改名	token 级 7/14，字节级 14/14 失败
同时，策略 B 唯一漏掉 `spo0`，策略 D 唯一漏掉 `spo12`，两者的失败集不同，说明数据能有效区分这两种赋值规则。

程序工程健壮性（V2/V4/V6/V9）：main.cpp/py 仅包含常量 {0, 1, 2} 或相关边界，与输出无重叠，确认无硬编码 (V2)；结构不变量检查均吻合，非 NIE 的合法 .out 恰有 $n$ 行、升序且每党恰 1 名 (V4)；暴力对拍 3000 组小数据以及 Python 对拍 C++ 均为 0 分歧 (V6)；UBSan/stderr 检测全空，-ftrapv 校验通过 (V9)。
规模与边界分析：最大数据规模达到 $n=8000$ ， $m=20000$ （即 16000 结点与 40000 边）；不存在 $n=0$ 或 $m=0$ 的数据；测试集中未出现自环（ $a=b$ ）；唯一的重复厌恶对存在于 spo13 中（共 23 条重复，这也是数据可疑的旁证）。
NIE 测试点：全部数据中恰好存在 3 个无解点，即 spo4、spo5 和 spo6。
.out 的生成方式：评测环境下没有找到 data.py 等数据生成器，因此无法追查 spo13.out 非法数据的原始生成方式。

「一本通 3.5 练习 5」和平委员会

目录

形式化题目

正解

思路

代码

复杂度

总结