形式化题目

给定有向图 $G=(V,E)$，$V=\{1,2,\dots,n\}$，每条边都从编号小的点指向编号大的点，且对每个点 $i$，集合

本身是一个团（输入可能含重边）。对点集 $T$：

• 团：$T$ 中任意两点之间都有边（方向为小编号指向大编号），空集也算团；
• 可扩团：存在一个点，与 $T$ 中每个点之间都有边；
• 极大团：不是可扩团的团，即不能再加入任何点的团（空团总可以再加入任意一点，所以极大团都是非空团）。

求 $G$ 中不同极大团的个数。

样例输入对应的有向图如下，它同时演示了题设性质：$H[3]=\{1,2\}$、$H[4]=\{2,3\}$ 都是团。

digraph G {
  rankdir=LR;
  node [shape=circle];
  1 -> 2;
  1 -> 3;
  2 -> 3;
  2 -> 4;
  3 -> 4;
}

样例的两个极大团是 $\{1,2,3\}$ 和 $\{2,3,4\}$；$\{1,2\}$ 虽然是团，但还能加入点 3，所以是可扩团，不计入答案。

正解

思路

朴素做法。 枚举所有点集，逐一判断“是否为团、是否还能扩大”，复杂度 $O(2^n\cdot n^2)$，只够 $n\leqslant 10$ 的数据。瓶颈在于候选团有指数多个：$n$ 高达 $10^6$，必须放弃“枚举团”，改为把极大团与 $O(n)$ 个、每个 $O(1)$ 可判定的对象一一对应。

第一步：把每个团挂到它的最大点上。 对点 $i$ 定义

由题设 $H[i]$ 是团，且 $i$ 与 $H[i]$ 中每点之间都有边（方向由 $H[i]$ 指向 $i$），所以 $P(i)$ 是团。反过来，任何包含 $i$ 的团 $T$，其余点都比 $i$ 小且与 $i$ 相邻，即 $T\setminus\{i\}\subseteq H[i]$，故 $T\subseteq P(i)$。也就是说，$P(i)$ 就是“包含 $i$ 的最大团”。

由此得到一一对应：任取团 $T$，设 $i$ 是 $T$ 的最大点，则 $T\subseteq P(i)$；若 $T$ 极大，必有 $T=P(i)$。而 $P(i)$ 的最大点恰好是 $i$，所以不同点给出的 $P(i)$ 互不相同。于是

第二步：包含关系只需向后检查。 若 $j<i$，则 $P(j)$ 中所有元素都不超过 $j<i$，于是 $i\notin P(j)$，不可能有 $P(i)\subseteq P(j)$。所以 $P(i)$ 若被包住，只可能被某个 $j>i$、且存在边 $i\to j$ 的 $P(j)$ 包住，条件是 $H[i]\subseteq H[j]\cup\{j\}$。逐条出边做这样的集合包含，最坏要 $O(nm)$，还要再压。

第三步：用入度比较代替集合包含（关键）。 记 $j=last[i]=\max H[i]$（最大前驱）。因为 $H[i]$ 是团，$H[i]$ 中除 $j$ 外的每个前驱 $p$ 都满足 $p<j$ 且 $p\to j$，即 $p\in H[j]$，所以恒有

• 充分：若 $|H[i]|>|H[j]|$，由 (1) 只能是 $|H[i]|=|H[j]|+1$ 且 $H[j]=H[i]\setminus\{j\}$，于是 $P(j)=\{j\}\cup H[j]\subseteq H[i]\cup\{i\}=P(i)$，即 $j$ 的团被 $i$ 吸收。
• 必要：若 $P(j)\subseteq P(i)$（此时 $j<i$、边 $j\to i$），则 $j\in H[i]$，且 $H[j]$ 的元素都小于 $j<i$、不会等于 $i$，故 $H[i]\supseteq H[j]\cup\{j\}$。从 $v_0=i$ 出发令 $v_{t+1}=last[v_t]$：由 (1) 同样的理由 $H[v_{t+1}]\supseteq H[v_t]\setminus\{v_{t+1}\}$，而 $v_{t+1}>j$ 不会削掉 $H[j]\cup\{j\}$ 的任何元素，故归纳地 $H[v_t]\supseteq H[j]\cup\{j\}$。该序列严格递减且始终满足 $last[v_t]\geqslant j$（因为 $j\in H[v_t]$），有限步后必有某步 $last[v_{t-1}]=j$，此时 $|H[v_{t-1}]|\geqslant|H[j]|+1>|H[j]|$，$j$ 按判据被标记。

于是得到充要判据：

第四步：重边先去重。 判据里的 $|H[i]|$ 是不同前驱的个数，重边会把计数撑高、破坏 (1)。把每条边压成整数 a<<20|b（$n\leqslant 10^6<2^{20}$）后排序，相同边相邻、跳过即可去重；排序还让同一个 $b$ 的前驱按 $a$ 升序出现，最后一次写入恰好就是 $last[b]$。

扫描与答案。 按 $i=1,\dots,n$ 扫一遍：$last[i]\neq 0$ 且 $|H[i]|>|H[last[i]]|$ 时标记 $last[i]$，最后输出 $n-$ 被标记点数。下表是样例的完整计算，其中 $d(i)=|H[i]|$ 表示不同前驱个数：

被标记的是 1、2：$P(1)=\{1\}\subseteq P(2)$、$P(2)=\{1,2\}\subseteq P(3)$，它们都被更大的团包住；未标记的 3、4 给出两个极大团 $\{1,2,3\}$ 与 $\{2,3,4\}$，答案为 2，与样例输出一致。

实现里 packed 是压成 a<<20|b、排序去重后的边表，pred_cnt/pred_max 依次存 $|H[i]|$ 与 $last[i]$，covered 存上表最后一列的标记结果，三者与上述推导一一对应。

代码

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#!/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-02 18:30
# update_at: 2026-10-02 18:30

import sys
from array import array

SHIFT = 20  # 点编号 n<=1e6<2^20，a<<20|b 把一条边压成一个整数，排序后顺带去重
SPAN = 1 << SHIFT


def solve() -> None:
    src = sys.stdin.buffer
    n, m = map(int, next(src).split())
    packed = [0] * m
    for i in range(m):
        a, b = map(int, next(src).split())
        packed[i] = a << SHIFT | b  # a 占高位、b 占低 20 位，按 (a, b) 字典序排序
    packed.sort()

    # 排序后相同边相邻：pred_cnt 记去重后的前驱数 |H[i]|，pred_max 记最大前驱 last[i]
    pred_cnt = array("i", [0]) * (n + 1)
    pred_max = array("i", [0]) * (n + 1)
    seen = -1
    for key in packed:
        if key != seen:
            seen = key
            b = key & (SPAN - 1)
            pred_cnt[b] += 1
            pred_max[b] = key >> SHIFT  # 同一个 b 的 key 按 a 升序，最后一次即最大前驱

    # P(i)={i}∪H[i] 是包含 i 的最大团。H[i]\{last[i]} ⊆ H[last[i]] 恒成立，
    # 所以 |H[i]|>|H[last[i]]| 等价于 H[i]=H[last[i]]∪{last[i]}=P(last[i])，
    # 即 P(last[i]) 整个被 i 吸收 → last[i] 对应的团被包住，不是极大团。
    covered = bytearray(n + 1)
    for i in range(1, n + 1):
        j = pred_max[i]
        if j and pred_cnt[i] > pred_cnt[j]:
            covered[j] = 1
    print(n - sum(covered))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-04 23:06
 * update_at: 2026-10-04 23:06
 */
// main.cpp：roj 10022 网络
// 题设保证每个点的前驱集合 H[i] 是团，即编号 1..n 是弦图的一个完美消除序列。
// 记 P(i) = {i} ∪ H[i]，它是包含 i 的最大团；极大团恰好是那些不被其它 P(j) 包住的 P(i)。
// 若 j = last[i]（i 的最大前驱），由 H[i] 是团可得 H[i]\{j} ⊆ H[j]，
// 于是 |H[i]| > |H[j]| 等价于 P(j) ⊆ P(i)，即 j 对应的团被 i 吸收。
// 所以按 i 扫一遍、用一次整数比较标记被吸收的 j，答案就是 n 减去被标记点的个数。
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;

const ll MAXN = 1000005; // n <= 1e6
const ll MAXM = 1000005; // m <= 1e6
const ll SHIFT = 20;     // n <= 1e6 < 2^20，把一条边压成 a<<SHIFT|b

ll n, m;
ll packed_edge[MAXM]; // 每条边压缩为 a<<SHIFT|b，排序后既去重、又保证同一终点的前驱按起点升序
int pred_cnt[MAXN];   // pred_cnt[i] = |H[i]|，去重后 i 的不同前驱个数（<= 1e6，用 int 省内存）
int pred_max[MAXN];   // pred_max[i] = max H[i]，即 i 的最大前驱 last[i]，0 表示没有前驱
char covered[MAXN];   // covered[j] = 1 表示 P(j) 被更大的团包住，不是极大团（标记只有 0/1，用 char）

const int BUF_SIZE = 1 << 20;
char in_buf[BUF_SIZE]; // fread 输入缓冲：最多 2e6 个整数，cin 会超时
int buf_pos = 0, buf_len = 0;

// 从缓冲区取一个字符，缓冲区读空时用 fread 续读；输入结束返回 -1。
int read_char() {
    if (buf_pos == buf_len) {
        buf_len = fread(in_buf, 1, BUF_SIZE, stdin);
        buf_pos = 0;
        if (buf_len <= 0) return -1;
    }
    return in_buf[buf_pos++];
}

// 快读一个非负整数。
ll read_int() {
    int c = read_char();
    while (c <= ' ' && c != -1) c = read_char();
    ll x = 0;
    while (c > ' ') {
        x = x * 10 + (c - '0');
        c = read_char();
    }
    return x;
}

void read_input() {
    n = read_int();
    m = read_int();
    for (ll i = 0; i < m; i++) {
        ll a = read_int();
        ll b = read_int();
        packed_edge[i] = (a << SHIFT) | b; // a 占高位、b 占低 20 位，按 (a,b) 字典序排序
    }
}

int main() {
    read_input();

    sort(packed_edge, packed_edge + m);

    // 排序后相同边相邻，跳过重复边完成去重；
    // 同一个终点 b 的边按起点 a 升序出现，最后一次写入的 a 就是最大前驱。
    ll seen = -1;
    for (ll i = 0; i < m; i++) {
        if (packed_edge[i] == seen) continue;
        seen = packed_edge[i];
        int b = packed_edge[i] & ((1 << SHIFT) - 1);
        pred_cnt[b] = pred_cnt[b] + 1;
        pred_max[b] = packed_edge[i] >> SHIFT;
    }

    // P(i) = {i} ∪ H[i] 是包含 i 的最大团，极大团与未被包住的 P(i) 一一对应。
    // 若 last[i] = j 且 |H[i]| > |H[j]|，则 H[i] = H[j] ∪ {j}，有 P(j) ⊆ P(i)，j 被吸收。
    for (ll i = 1; i <= n; i++) {
        int j = pred_max[i];
        if (j != 0 && pred_cnt[i] > pred_cnt[j]) {
            covered[j] = 1;
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (covered[i] == 0) ans = ans + 1;
    }
    printf("%lld\n", ans);

    return 0;
}

复杂度

时间复杂度 $O(m\log m)$：读入与两次扫描都是 $O(n+m)$，排序去重是主项；空间复杂度 $O(n+m)$，边表与三个计数数组各占线性空间。与参考 C++ 正解同为“排序 + 一次扫描”，只是把集合包含判定换成了入度的一次整数比较。

总结

本题的钥匙是题设“$H[i]$ 是团”（即编号顺序是完美消除序列，图是弦图）：它让每个点的 $P(i)=\{i\}\cup H[i]$ 成为包含该点的最大团，从而极大团与“不被其他 $P(j)$ 包住的 $P(i)$”一一对应。再利用团内任意两点相邻推出的计数关系 $|H[i]|\leqslant|H[last[i]]|+1$，把集合包含判定压成一次整数比较，整个问题就落成“排序去重 + 两遍线性扫描”。