[BalticOI 2003] 团伙 (Day 2)

GitHub跳转原题关系图返回列表

用并查集维护强制朋友关系，答案是朋友关系图的连通分量个数；2N 并查集是其紧凑模板写法。

OJ: luogu

题目 ID: P1892

难度:普及+/提高

标签:并查集种类并查集连通分量关系传递pythoncpp

日期: 2026-07-16 18:26

目录

  1. 题意
  2. 思路
    1. 写法一：建朋友图 + 并查集数连通分量
    2. 写法二：2N 并查集（正式提交 / 模板写法）
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

n 个人之间有朋友 F 或敌人 E 关系。朋友的朋友是朋友，敌人的敌人也是朋友。朋友必须在同一团体，求最多能有多少个团体。

思路

本质是：把「必须同团」的人连成图，再数连通分量。每个连通分量是一群被规则强制为朋友的人；让每群单独成团，分量个数就是最大团体数。

写法一：建朋友图 + 并查集数连通分量

更贴近题意，适合作为第一版理解：

  1. 读到 F a b：在朋友图里连边 a -- b（并查集 union）。
  2. 读到 E a b：先记下敌人列表。
  3. 对每个人，把他的所有敌人两两连边——因为「敌人的敌人是朋友」。
  4. 统计 1..n 的连通分量个数。

Python：

python
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])

    # 并查集建「朋友关系图」：同一连通分量 = 必须在同一团伙
    parent = list(range(n + 1))
    size = [1] * (n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # 先记下每个人的敌人列表；朋友直接连边
    enemies = [[] for _ in range(n + 1)]
    pos = 2
    for _ in range(m):
        relation = data[pos]
        a, b = int(data[pos + 1]), int(data[pos + 2])
        pos += 3
        if relation == b"F":
            union(a, b)  # 朋友：图中连一条边
        else:
            enemies[a].append(b)
            enemies[b].append(a)

    # 敌人的敌人是朋友：同一个人的所有敌人两两连边
    for person in range(1, n + 1):
        es = enemies[person]
        if len(es) < 2:
            continue
        first = es[0]
        for other in es[1:]:
            union(first, other)

    # 连通分量个数 = 最多团伙数
    print(len({find(i) for i in range(1, n + 1)}))


if __name__ == "__main__":
    main()

C++：

cpp
/**
 * 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-19 11:44
 * update_at: 2026-07-19 11:44
 */
// main2.cpp：建朋友关系图 + 并查集数连通分量（教学版）
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
int parent[MAXN];
int sz[MAXN];
vector<int> enemies[MAXN]; // enemies[i]：i 的直接敌人列表

int find_root(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

void unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) {
        return;
    }
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    parent[b] = a;
    sz[a] += sz[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    for (int i = 1; i <= m; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'F') {
            // 朋友：图中直接连边
            unite(a, b);
        } else {
            // 敌人：先记下来，后面统一处理
            enemies[a].push_back(b);
            enemies[b].push_back(a);
        }
    }

    // 敌人的敌人是朋友：同一个人的所有敌人两两并到同一集合
    for (int person = 1; person <= n; person++) {
        int cnt = (int)enemies[person].size();
        if (cnt < 2) {
            continue;
        }
        int first = enemies[person][0];
        for (int j = 1; j < cnt; j++) {
            unite(first, enemies[person][j]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find_root(i) == i) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

写法二：2N 并查集（正式提交 / 模板写法）

为每个人建立对立侧节点：

  • x 表示人物 x；
  • x+n 表示与 x 对立的一侧。

规则：

  • F a b：只合并 a 与 b；
  • E a b：合并 a 与 b+n，以及 b 与 a+n。

若两人有共同敌人，会通过对立侧落到同一集合，自动得到「敌人的敌人是朋友」。最后只统计真实人物 1..n 的不同代表元。

注意：朋友关系时不要再合并 a+n 与 b+n。多合并对立侧会把不该同团的人连起来，答案偏小（容易只得部分分）。

Python 知识

  • 并查集用列表 parent / size，循环路径压缩不受递归深度限制。
  • {find(i) for i in range(1, n + 1)} 用集合推导式统计连通分量。
  • 关系 token 可保留为 bytes，直接与 b"F" 比较。
  • 敌人列表 enemies[i] 是「按点存邻接」，再统一连边。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合推导式与去重。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：迭代替代深递归。

代码

正式提交用 2N 并查集。

Python：

python
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    # x: 人物 x；x+n: 与 x 对立的一侧
    parent = list(range(2 * n + 1))
    size = [1] * (2 * n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    pos = 2
    for _ in range(m):
        relation = data[pos]
        a, b = int(data[pos + 1]), int(data[pos + 2])
        pos += 3
        if relation == b"F":
            # 朋友：只合并真人，不要合并对立侧
            union(a, b)
        else:
            # 敌人：a 与 b 的对立侧同组，b 与 a 的对立侧同组
            # 从而「有共同敌人」的人会落到同一集合
            union(a, b + n)
            union(b, a + n)

    print(len({find(person) for person in range(1, n + 1)}))


if __name__ == "__main__":
    main()

C++：

cpp
/**
 * 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-19 11:44
 * update_at: 2026-07-19 11:44
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
int parent[MAXN * 2]; // x: 真人 x；x+n: x 的对立侧
int sz[MAXN * 2];

int find_root(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

// 按秩（按大小）合并
void unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) {
        return;
    }
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    parent[b] = a;
    sz[a] += sz[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    for (int i = 1; i <= m; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'F') {
            // 朋友：只合并真人
            unite(a, b);
        } else {
            // 敌人：a 与 b 的对立侧同组，b 与 a 的对立侧同组
            unite(a, b + n);
            unite(b, a + n);
        }
    }

    // 统计 1..n 的连通分量个数
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find_root(i) == i) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度

  • 写法一：处理敌人两两连边时，每人敌人很少，总复杂度仍可视为 O((n+m)α(n))O((n+m)\alpha(n)) 量级（本题 n≤1000n \le 1000 足够）。
  • 写法二：每条关系常数次合并，时间 O((n+m)α(n))O((n+m)\alpha(n))，空间 O(n)O(n)。

总结

这题正解就是并查集。先想成「建强制朋友关系图，数连通分量」；再压缩成 2N 种类并查集模板。

  • main2.py / main2.cpp：教学版（敌人列表 + 连通分量）
  • main.py / main.cpp：正式版（2N 并查集）