M07734: 虫子的生活

DSU, DFS/BFS 染色, http://cs101.openjudge.cn/practice/07734/

Hopper 博士正在研究一种罕见种类的虫子的性行为。他假定虫子只表现为两种性别，并且虫子只与异性进行交互。在他的实验中，不同的虫子个体和虫子的交互行为很容易区分开来，因为这些虫子的背上都被标记有一些标号。

现在给定一系列的虫子的交互，现在让你判断实验的结果是否验证了他的关于没有同性恋的虫子的假设或者是否存在一些虫子之间的交互证明假设是错的。

输入

输入的第一行包含实验的组数。每组实验数据第一行是虫子的个数（至少1个，最多2000个) 和交互的次数 (最多1000000次) ，以空格间隔. 在下面的几行中,每次交互通过给出交互的两个虫子的标号来表示，标号之间以空格间隔。已知虫子从1开始连续编号。

输出

每组测试数据的输出为2行，第一行包含 "Scenario #i:", 其中 i 是实验数据组数的标号，从1开始,第二行为 "No suspicious bugs found!" 如果实验结果和博士的假设相符,或 "Suspicious bugs found!" 如果Hopper的博士的假设是错误的

样例输入

样例输出

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

注意每组数据中间有个空行

扩展域并查集

1. 什么是扩展域并查集？

它的核心思想是：“如果一个虫子 $i$ 有两种可能的性别，我就给它开两个分身。”

对于每只虫子 $i$ ，我们拆分成两个节点：

$i$ ：代表 $i$ 是性别 A（比如雄性）。
$i + n$ ：代表 $i$ 是性别 B（比如雌性）。

2. 怎么处理交互（谈恋爱）？

如果题目说 虫子 $a$ 和虫子 $b$ 交互：按照“异性恋”假设，这意味着：

如果 $a$ 是性别 A，那么 $b$ 必须是性别 B。即：合并 $a$ 和 $b + n$ 。
如果 $a$ 是性别 B，那么 $b$ 必须是性别 A。即：合并 $a + n$ 和 $b$ 。

3. 怎么发现矛盾（同性恋）？

在合并之前，我们检查一下：

如果 $a$ 和 $b$ 已经在同一个集合里，说明它们必须是同性，但这和“它们正在交互”矛盾！
或者说：如果 find(a) == find(b)，说明它们是同性，发现可疑虫子！

4. 扩展域版本代码

python

import sys
sys.setrecursionlimit(1000000)


def solve():
    T = int(input())

    for case in range(1, T + 1):
        n, m = map(int, input().split())

        # 扩展域：1~n 表示性别A，n+1~2n 表示性别B
        parent = list(range(2 * n + 1))

        def find(i):
            if parent[i] == i:
                return i
            parent[i] = find(parent[i])
            return parent[i]

        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j

        suspicious = False
        for _ in range(m):
            u, v = map(int, input().split())
            if suspicious: continue

            # 如果 u 和 v 已经在同一个性别域里，说明他们是同性！
            if find(u) == find(v):
                suspicious = True
            else:
                # u 恋爱对象必须是 v 的异性分身
                union(u, v + n)
                # v 恋爱对象必须是 u 的异性分身
                union(v, u + n)

        print(f"Scenario #{case}:")
        if suspicious:
            print("Suspicious bugs found!")
        else:
            print("No suspicious bugs found!")
        print()


solve()

5. 两种方法的优缺点对比

特性	带权并查集 (Weighted DSU)	扩展域并查集 (Domain Extension)
理解难度	难。需要理解向量叠加或 XOR 逻辑。	易。就是逻辑上的“如果……那么……”推导。
代码量	略小，但合并公式 `color[ra] = ...` 极易写错。	略大（数组开 2 倍或 3 倍），但逻辑极简单。
空间复杂度	低。只需 $N$ 的空间。	高。需要 $2 \times N$ 或更多空间。
通用性	适合处理连续的数值关系（如： $a$ 比 $b$ 重 $w$ 克）。	适合处理有限的状态（如：性别、食物链的三种关系）。

总结建议：

如果状态数很少（比如这题只有 2 个性别，或者《食物链》里只有 3 种关系），永远优先使用扩展域并查集。
只有当空间限制非常严苛，或者关系种类特别多（比如 $N$ 种关系）时，才考虑带权并查集。

对于《虫子的生活》这道题，扩展域法是绝对的推荐方案，因为它不需要你计算任何数学公式，只需要把“敌人的敌人是朋友”这种逻辑翻译成代码即可。

带权并查集

带权并查集，维护每个节点与根节点的性别关系（0 同性别，1 异性别）。每次交互时若已在同一集合则检查是否矛盾，否则合并。

python

import sys
sys.setrecursionlimit(1000000)

def ints():
    for line in sys.stdin.buffer:
        for num in line.split():
            yield int(num)

def solve():
    it = ints()
    T = next(it)
    for case in range(1, T + 1):
        n = next(it); m = next(it)
        parent = list(range(n + 1))
        color = [0] * (n + 1)

        def find(x):
            if parent[x] != x:
                root = find(parent[x])
                color[x] ^= color[parent[x]]
                parent[x] = root
            return parent[x]

        suspicious = False
        for _ in range(m):
            a = next(it); b = next(it)
            if suspicious:
                continue
            ra, rb = find(a), find(b)
            if ra == rb:
                if color[a] == color[b]:
                    suspicious = True
            else:
                parent[ra] = rb
                color[ra] = color[a] ^ color[b] ^ 1

        print(f"Scenario #{case}:")
        print("Suspicious bugs found!" if suspicious else "No suspicious bugs found!")
        if case != T:
            print()

if __name__ == "__main__":
    solve()

既然你想要彻底攻克带权并查集，我们用最接地气的“帮派与辈分”来打比方，完全避开枯燥的数学推导。
第一步：并查集里，我们在存什么？
在普通并查集里，我们只记录 “谁是谁的老大”。而在带权并查集里，我们不仅记录老大，还多记录一件事：“我和我老大的性别，是相同还是相反？”
我们用 color[i] 来记录这个关系：
color[i] = 0：我和我老大性别相同。
color[i] = 1：我和我老大性别相反。
第二步：核心操作 1 —— 找老大（Path Compression）
当我们要知道 A 的最终老大是谁时，并查集会把 A 直接挂到最终老大 Boss 下面。在这个过程中，A 必须要更新它和 Boss 的性别关系。
假设有这样一个链条：
A $\to$ B (A的爸爸) $\to$ C (B的爸爸，也就是最终Boss)
已知 A 和 B 性别相反（color[A] = 1）。
已知 B 和 C 性别相反（color[B] = 1）。
现在要把 A 直接连到 C 身上。那么 A 和 C 的性别是相同还是相反？
常识推导：A 和 B 相反，B 和 C 相反，那 A 和 C 肯定相同。
代码实现：color[A] = color[A] ^ color[B]（即 1 ^ 1 = 0，相同）。
这就是 find 函数里这一行的意思： color[x] ^= color[parent[x]]它就是顺着辈分往上摸，把一路上所有的“相反关系”叠加起来，算出自己和最终老大的关系。
第三步：核心操作 2 —— 合并两个帮派（Union）
现在有两个独立的帮派，分别由老大 RA 和老大 RB 带领。 A 属于 RA 帮派，B 属于 RB 帮派。
突然，有人举报 A 和 B 在谈恋爱。这意味着 A 和 B 的性别必须相反。我们要把这两个帮派合并，让老大 RA 认 RB 做老大（parent[ra] = rb）。
既然 RA 认了 RB 做老大，那么 RA 和 RB 的性别是相同还是相反（即 color[ra] 应该填什么）？
我们来走一遍关系链（从 RA 走到 RB）：
从 RA 到 A：关系是 color[a]。
从 A 到 B：他们是情侣，关系是 1（相反）。
从 B 到 RB：关系是 color[b]。
把这三段路的关系加起来（用异或 ^ 累加）：
color[ra] = color[a] ^ 1 ^ color[b]
这一步，就是给两个帮派搭了一座桥，并确定了两个帮派老大之间的相对性别。
第四步：怎么发现矛盾？
如果 A 和 B 本来就在同一个帮派里（也就是说，他们有着共同的最终老大 R）。
我们已经知道了：
A 和老大 R 的关系（color[a]）
B 和老大 R 的关系（color[b]）
现在又有人举报 A 和 B 谈恋爱（即他们必须是异性）。我们做个检测：
如果 color[a] == color[b]：说明 A 和 B 相对于老大 R 的性别状态是一样的。那 A 和 B 必然是同性！
同性却在谈恋爱？矛盾发生了！ 判定为 Suspicious。
为什么这个方法很精妙？
因为我们不需要知道任何一只虫子具体是男是女。我们只记录“相对关系”：
你和你的直属上司是同性还是异性？
通过不断地把直属上司换成更大的 Boss（路径压缩），我们就能随时算出来任何两只虫子之间的相对性别。
一旦发现两只虫子在既有关系网里是“同性”，在现实中却在“恋爱”，谎言就被戳穿了。

python

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)


def solve_bug_life(scenarios):
    for i in range(1, scenarios + 1):
        n, m = map(int, input().split())
        uf = UnionFind(2 * n + 1)  # 为每个虫子创建两个节点表示其可能的两种性别
        suspicious = False
        for _ in range(m):
            u, v = map(int, input().split())
            if suspicious:
                continue

            if uf.is_connected(u, v):
                suspicious = True
            uf.union(u, v + n)  # 将u的一种性别与v的另一种性别关联
            uf.union(u + n, v)  # 同理


        print(f'Scenario #{i}:')
        print('Suspicious bugs found!' if suspicious else 'No suspicious bugs found!')
        print()


# 读取场景数量并解决问题
scenarios = int(input())
solve_bug_life(scenarios)

这是一个经典的二分图判定（Bipartite Graph Check）问题。

算法思路

根据题意，虫子只有两种性别，且只与异性进行交互。这意味着如果我们将虫子看作图中的点，交互看作边，那么这个图必须是一个二分图。

如果在实验结果中发现了“同性恋”倾向（即不符合假设），则说明图中存在奇环（Odd Cycle）。

为了高效解决这个问题，特别是面对多达 $1, 000, 000$ 次交互的情况，我们使用并查集（Disjoint Set Union, DSU），并采用“扩展节点”或“偏移量（加权并查集）”的技巧。

扩展节点法（2N 策略）：

为每个虫子 $i$ 创建两个节点： $i$ （代表性别A）和 $i + N$ （代表性别B）。
对于每一次交互 $(u, v)$ ：
- 检查 $u$ 和 $v$ 是否已经在同一个集合中。如果是，说明它们必须是同性，但现在发生了交互，违反了假设。
- 如果不在，则将 $u$ 与 $v + N$ 合并（说明 $u$ 和 $v$ 的异性属于同一类），将 $v$ 与 $u + N$ 合并。
这种方法能处理所有连通分量，并快速判断是否存在冲突。

优化：

路径减半（Path Halving）：p[i] = p[p[i]]，比递归快且避免栈溢出。
按秩合并（Union by Rank）：防止树退化。
快速 IO：使用 sys.stdin 迭代器处理百万级数据。

为了提高代码的可复用性并确保在处理 $1, 000, 000$ 条数据时的执行效率，我们将并查集（Union-Find）封装为一个高效的类。

python

import sys

class UnionFind:
    """高效并查集实现"""
    def __init__(self, size):
        # parent 数组，size 通常为 2*N + 1
        self.parent = list(range(size))
        # rank 数组用于按秩合并，减少树高度
        self.rank = [0] * size

    def find(self, i):
        """查找根节点，使用路径减半优化"""
        p = self.parent
        while p[i] != i:
            p[i] = p[p[i]] # 路径减半
            i = p[i]
        return i

    def union(self, root_i, root_j):
        """合并两个已知的根节点"""
        if root_i != root_j:
            p = self.parent
            r = self.rank
            if r[root_i] < r[root_j]:
                p[root_i] = root_j
            elif r[root_i] > r[root_j]:
                p[root_j] = root_i
            else:
                p[root_i] = root_j
                r[root_j] += 1
            return True
        return False

def solve():
    # 使用生成器读取所有输入，应对百万级数据，节省内存
    def get_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield int(word)
    
    tokens = get_tokens()
    
    try:
        num_scenarios = next(tokens)
    except StopIteration:
        return
    
    results = []
    
    for s in range(1, num_scenarios + 1):
        try:
            n = next(tokens)
            m = next(tokens)
        except StopIteration:
            break
            
        # 初始化并查集，大小为 2*n + 1 (扩展域：1..n 为 A，n+1..2n 为 B)
        uf = UnionFind(2 * n + 1)
        is_suspicious = False
        
        for _ in range(m):
            u = next(tokens)
            v = next(tokens)
            
            if is_suspicious:
                continue
            
            root_u = uf.find(u)
            root_v = uf.find(v)
            
            if root_u == root_v:
                # 发现 u 和 v 已经在同一个性别集合中
                is_suspicious = True
            else:
                # u 的性别与 v 的异性集合合并
                # v 的性别与 u 的异性集合合并
                root_u_opp = uf.find(u + n)
                root_v_opp = uf.find(v + n)
                uf.union(root_u, root_v_opp)
                uf.union(root_v, root_u_opp)
        
        # 记录结果
        results.append(f"Scenario #{s}:")
        if is_suspicious:
            results.append("Suspicious bugs found!")
        else:
            results.append("No suspicious bugs found!")
        # 按照题目样例，每组结果后输出一个空行
        results.append("")

    # 批量输出提高效率
    if results:
        sys.stdout.write("\n".join(results))

if __name__ == '__main__':
    solve()

代码解读：
UnionFind 类：
__init__：初始化 parent 数组。
find：通过循环实现路径减半。相比递归，它在 Python 中更有效率且不会触碰递归深度限制。
union：接收两个已经过 find 的根节点。在主循环中先判断 root_u == root_v 再调用 union，可以减少重复计算。
扩展域逻辑：
我们不关心具体的性别是男是女，只关心“相对关系”。
如果 $u$ 与 $v$ 交互，那么 $u$ 与 $v + N$ （ $v$ 的异性）必定属于同一类。
并查集维护的是“同类”关系。
性能点：
next(tokens)：使用 sys.stdin 构造的生成器在处理 $2 \times 10^{6}$ 个整数时非常快。
results.append + "\n".join：避免了频繁的 print 调用产生的 IO 耗时。
if is_suspicious: continue：一旦在当前实验中发现冲突，后续的交互记录只需读入而无需再进行复杂的并查集运算，显著加快运行速度。

染色法

DFS 染色法是将问题转化为二分图判定。核心思想：

染色原理：尝试给图中的每个节点（虫子）染上两种颜色之一（代表两种性别，比如 0 和 1）。
规则：如果给节点 $u$ 染色为 $0$ ，那么与 $u$ 直接相连（有交互）的所有节点 $v$ 都必须染色为 $1$ 。反之亦然。
冲突检测：如果在染色的过程中，发现某个节点 $v$ 已经被染过色了，且它的颜色和它邻居 $u$ 的颜色相同，说明出现了“同性交互”，即该图不是二分图。

python

import sys


def solve(t_case):
    line = input().split()
    while not line:
        line = input().split()
        if not line: return
    n, m = map(int, line)

    # 优化点：预先创建 1-N 的整数对象。
    # 这样在 adj[u].append(nodes[v]) 时，存储的是这 2000 个对象的引用，
    # 而不是每次 input 产生的新的整数对象。
    nodes = list(range(n + 1))

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        # 这里的 nodes[v] 和 nodes[u] 是关键
        adj[u].append(nodes[v])
        adj[v].append(nodes[u])

    # sex[i] 存储性别：-1 表示未染色，0 和 1 表示两种性别
    sex = [-1] * (n + 1)
    is_suspicious = False

    # 遍历所有节点，处理不连通的情况
    for i in range(1, n + 1):
        if is_suspicious:
            break

        if sex[i] == -1:
            # 发现未染色的连通分量，开始迭代式 DFS
            stack = [i]
            sex[i] = 0  # 初始颜色设为 0

            while stack:
                curr = stack.pop()

                for neighbor in adj[curr]:
                    if sex[neighbor] == -1:
                        # 如果邻居没染色，染上相反的颜色
                        sex[neighbor] = 1 - sex[curr]
                        stack.append(neighbor)
                    elif sex[neighbor] == sex[curr]:
                        # 如果邻居已染色且颜色相同，发现冲突
                        is_suspicious = True
                        break
                if is_suspicious:
                    break

    sys.stdout.write(f"Scenario #{t_case}:\n")
    sys.stdout.write("Suspicious bugs found!\n\n" if is_suspicious else "No suspicious bugs found!\n\n")


def main():
    line = input().strip()
    if line:
        for i in range(1, int(line) + 1):
            solve(i)


if __name__ == "__main__":
    main()

需要注意：
递归深度：Python 默认递归深度较浅（1000），而虫子有 2000 个，如果递归需要 sys.setrecursionlimit。
性能优化：对于 $10^{6}$ 条边，邻接表的构建和遍历压力很大。迭代式 DFS（用栈模拟）通常比递归式 DFS 在 Python 中更快且更安全。
快速 IO：使用 sys.stdin.read().split() 批量读取。

总结：算法复杂度为 $O (N + M)$ ，其中 $N$ 是虫子数， $M$ 是交互数。对于 $N = 2000, M = 1, 000, 000$ 的规模，DFS 染色法和并查集法在效率上非常接近，都是解决此题的标准方案。

思路：dfs 染色。构建邻接表。C++对内存的控制紧凑，AC。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int cnt = 1;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    while (m--) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(n, false);
    vector<int> sex(n, -1);
    auto dfs = [&](auto&& self, int u, int p) -> void {
        vis[u] = true;
        for (int v : adj[u]) {
            if (v == p || vis[v]) continue;
            if (sex[v] == -1) sex[v] = 1 - sex[u];
            self(self, v, u);
        }
    };

    for (int i = 0; i < n; i++) {
        if (sex[i] == -1) {
            sex[i] = 0;
            dfs(dfs, i, -1);
        }
    }

    bool flag = true;
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            if (sex[v] == sex[u]) {
                flag = false;
                break;
            }
        }
    }

    cout << "Scenario #" << cnt << ":\n";
    if (flag) {
        cout << "No suspicious bugs found!\n\n";
    } else {
        cout << "Suspicious bugs found!\n\n";
    }
    cnt++;
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

BFS染色

python

import sys
from collections import deque

input = sys.stdin.readline

def solve(t_case):
    line = input().split()
    while not line:
        line = input().split()
        if not line: return
    num, sex = map(int, line)

    # 优化点：预先创建 1-N 的整数对象。
    # 这样在 adj[u].append(nodes[v]) 时，存储的是这 2000 个对象的引用，
    # 而不是每次 input 产生的新的整数对象。
    nodes = list(range(num + 1)) 
    
    adj = [[] for _ in range(num + 1)]
    for _ in range(sex):
        u, v = map(int, input().split())
        # 这里的 nodes[v] 和 nodes[u] 是关键
        adj[u].append(nodes[v])
        adj[v].append(nodes[u])

    gender = [0] * (num + 1)
    suspicious = False

    for i in range(1, num + 1):
        if suspicious: break
        if gender[i] == 0:
            gender[i] = 1
            queue = deque([i])
            q_pop = queue.popleft
            q_add = queue.append
            
            while queue:
                curr = q_pop()
                curr_sex = gender[curr]
                target_sex = 3 - curr_sex
                
                for neighbor in adj[curr]:
                    if gender[neighbor] == 0:
                        gender[neighbor] = target_sex
                        q_add(neighbor)
                    elif gender[neighbor] == curr_sex:
                        suspicious = True
                        break
                if suspicious: break
    
    sys.stdout.write(f"Scenario #{t_case}:\n")
    sys.stdout.write("Suspicious bugs found!\n\n" if suspicious else "No suspicious bugs found!\n\n")

def main():
    line = input().strip()
    if line:
        for i in range(1, int(line) + 1):
            solve(i)

if __name__ == '__main__':
    main()

M07734: 虫子的生活 ​

扩展域并查集 ​

带权并查集 ​

染色法 ​

M07734: 虫子的生活

扩展域并查集

带权并查集

染色法