团伙(group)

形式化题目

给定 $n$ 个元素 $1, 2, \dots, n$ 以及 $m$ 条二元关系：

关系 1（同类关系）： $x$ 与 $y$ 属于同一集合（朋友）；
关系 2（对立关系）： $x$ 与 $y$ 互为对立（敌人）。

满足以下规则：

若 $x, y$ 同属于同一集合且 $y, z$ 属于同一集合，则 $x, z$ 属于同一集合；
若 $x, y$ 互为对立且 $y, z$ 互为对立，则 $x, z$ 属于同一集合。

若无额外推导要求两个元素必须处于同一集合，则它们可以分别处于不同集合。求在满足所有关系的前提下，最多能划分为多少个互不相交的非空集合（即最大团伙数）。

题目解析

观察与建模

根据题意，朋友关系具有等价关系的传递性，可以直接用并查集进行合并。而敌人关系满足“敌人的敌人是我的朋友”，即对立关系的二次对立会变回同类关系。

这是一种典型的二分对立结构。对于每个人 $x$ ，我们可以建立两个域（种类并查集 / 扩展域并查集）：

同类域（朋友域）：编号为 $x$ （范围 $1 \sim n$ ）；
对立域（敌人域）：编号为 $x + n$ （范围 $n+1 \sim 2n$ ）。

关系处理方式如下：

$x$ 和 $y$ 是朋友（ $p = 0$ ）：
- 直接将 $x$ 和 $y$ 的朋友域合并，即 unite(x, y)。
$x$ 和 $y$ 是敌人（ $p = 1$ ）：
- $x$ 与 $y$ 的对立域合并：unite(x, y + n)，表示“ $y$ 的敌人是 $x$ 的朋友”；
- $y$ 与 $x$ 的对立域合并：unite(y, x + n)，表示“ $x$ 的敌人是 $y$ 的朋友”。

通过这样的合并，如果有“ $x$ 与 $y$ 是敌人，且 $y$ 与 $z$ 是敌人”：

$x$ 会与 $y + n$ 合并；
$z$ 会与 $y + n$ 合并；
此时 $x$ 和 $z$ 天然在同一个连通块内，自动完成了“敌人的敌人是朋友”的传递。

样例图示

以输入样例为例：

$n = 6, m = 4$
1 1 4（1 和 4 是敌人）：合并 $1$ 与 $4+6=10$ ， $4$ 与 $1+6=7$ ；
0 3 5（3 和 5 是朋友）：合并 $3$ 与 $5$ ；
0 4 6（4 和 6 是朋友）：合并 $4$ 与 $6$ ；
1 1 2（1 和 2 是敌人）：合并 $1$ 与 $2+6=8$ ， $2$ 与 $1+6=7$ 。

观察此时的连通性：

节点 $2$ 与 $1+6=7$ 连通，而节点 $4$ 也与 $1+6=7$ 连通，因此节点 $2$ 和 $4$ 间接成为朋友。
又因为节点 $4$ 和 $6$ 是朋友，所以 $\{2, 4, 6\}$ 同属一个团伙。
节点 $3$ 和 $5$ 同属一个团伙 $\{3, 5\}$ 。
节点 $1$ 独立成为一个团伙 $\{1\}$ 。

总共有 3 个团伙： $\{1\}$ 、 $\{3, 5\}$ 、 $\{2, 4, 6\}$ 。

graph TD
    subgraph 团伙 1
        1[1 号]
    end
    subgraph 团伙 2
        3[3 号] --- 5[5 号]
    end
    subgraph 团伙 3
        4[4 号] --- 6[6 号]
        2[2 号] -.-|敌人的敌人| 4
    end

统计答案

由于未被强制关联的人应尽可能独立以使团伙数最大，只需统计前 $n$ 个节点（即每个人自身的朋友域节点 $1 \sim n$ ）在并查集中有多少个互不相同的根节点（代表元）。

代码

Python 版：

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#!/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-07-05 21:47
# update_at: 2026-10-13 22:28

import sys


class DSU:
    """并查集 (Disjoint Set Union)"""

    def __init__(self, n: int):
        # 1-indexed, fa 初始指向自己，sz 初始为 1
        self.fa = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, x: int) -> int:
        """查找根节点，两趟路径压缩：先走到根，再把整条路径挂到根上"""
        root = x
        while self.fa[root] != root:
            root = self.fa[root]
        while self.fa[x] != root:
            self.fa[x], x = root, self.fa[x]
        return root

    def same(self, x: int, y: int) -> bool:
        """判断 x 和 y 是否属于同一个集合"""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        """按大小合并两个集合 (小树挂大树)；已在同一集合返回 False"""
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx
        self.fa[fy] = fx
        self.sz[fx] += self.sz[fy]
        return True


def solve() -> None:
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    it = iter(tokens)
    n = int(next(it))
    m = int(next(it))

    # 扩展并查集：1..n 为自身（朋友域），n+1..2n 为敌人域（对立域）
    dsu = DSU(2 * n)

    for _ in range(m):
        opt = int(next(it))
        x = int(next(it))
        y = int(next(it))
        if opt == 0:
            dsu.unite(x, y)
        else:
            # 敌人的敌人是朋友：x 的敌人与 y 合并，y 的敌人与 x 合并
            dsu.unite(x, y + n)
            dsu.unite(y, x + n)

    # 统计 1..n 中不同集合代表元的数量即为最大团伙数
    ans = len({dsu.find(i) for i in range(1, n + 1)})
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 00:20
 * update_at: 2026-10-13 22:34
 */

#include <cstdio>
#include <algorithm>

using namespace std;

// 并查集竞赛精简版（不用 struct）：路径压缩 + 按大小合并
// 口诀：find 找根压到底，unite 小树挂大树
// 易错点：init 别只写 fa[i] = i，sz[i] 也要置 1；合并后 sz 只在新根上有效
// 和别的模板一起用时 maxn 只留一份

const int maxn = 4015;   // 视数据范围调整为 2*最大n+5，本题 n <= 2005
int fa[maxn], sz[maxn];  // sz[x] 仅在根上有效

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

// 查 x 的根，顺手把整条链压到根上
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool same(int x, int y) { return find(x) == find(y); }

// 小树挂大树，返回是否真的发生了合并
bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
    return true;
}

// 扩展域并查集：节点 1..n 为自身（朋友域），n+1..2n 为敌对域
int n, m, ans;
bool root_seen[maxn];  // root_seen[r] 表示代表元 r 是否已经统计过

int main() {
    scanf("%d %d", &n, &m);

    // 初始化：每个人有自身域 x 和敌对域 x+n
    init(2 * n);

    for (int i = 1; i <= m; ++i) {
        int p, x, y;
        scanf("%d %d %d", &p, &x, &y);
        if (p == 0) {
            // 朋友：朋友的朋友是朋友，直接合并自身域
            unite(x, y);
        } else {
            // 敌人：x 与 y 的敌对域合并，y 与 x 的敌对域合并
            // 这样“敌人的敌人”会通过共同的敌对域节点自动连通
            unite(x, y + n);
            unite(y, x + n);
        }
    }

    // 统计 1..n 中不同 find(i) 的个数，就是最大团伙数
    // 注意：代表元可能落在敌对域（合并方向导致），所以要按根去重
    for (int i = 1; i <= n; ++i) {
        int r = find(i);
        if (!root_seen[r]) {
            root_seen[r] = true;
            ans = ans + 1;
        }
    }
    printf("%d\n", ans);

    return 0;
}

复杂度分析

时间复杂度： $\mathcal{O}((n + m) \cdot \alpha(n))$ 。初始化需要 $\mathcal{O}(n)$ ，每个关系执行常数次带路径压缩的并查集操作，均摊复杂度为反阿克曼函数 $\alpha(n)$ ，完全在 $1000\text{ ms}$ 时限内轻松通过。
空间复杂度： $\mathcal{O}(n)$ 。扩展域并查集数组大小为 $2n + 1$ ，占用内存极少，符合 $128\text{ MB}$ 的限制。

总结

本题是**种类并查集（扩展域并查集）**的经典模板题。核心思想是将具有二元对立关系的问题拆解为“同类域”与“对立域”，通过“ $x$ 与 $y$ 的对立域合并”来实现“敌人的敌人是朋友”的自然传递。

目录