#5460. 「ROI 2012 Day 2」剧院始于演员 题解

问题分析

我们有 $N$ 个演员和 $M$ 幕演出，每幕有一些演员参与。观众通过观察哪些演员一起出现在舞台上，来推断演员与肖像的对应关系。

关键观察：如果两个演员从未同时出现在舞台上，那么他们可能是同一个人（对应同一幅肖像），也可能是不同的人。只有当能唯一确定对应关系时才算"确定"。

核心思路

图论建模

将问题转化为图论问题：

• 每个演员是一个节点
• 如果两个演员在同一幕中出现，则在它们之间连边
• 这样会形成若干个连通分量

在同一个连通分量中的演员，可以通过他们的共同出现关系来区分。但在不同连通分量中的演员无法直接比较。

确定身份的时机

一个演员的身份在以下时刻被确定：

1. 直接确定：当某个连通分量中的演员数量等于该分量中不同的"角色"数量时
2. 间接确定：当通过排除法可以唯一确定时

更精确地说：

• 设 $C$ 是一个连通分量
• 设 $S$ 是该分量中出现的所有演员集合
• 当 $|S| = |C|$ 时，分量中的每个演员都可以唯一确定

算法框架

1. 构建连通分量：使用并查集，将同一幕中出现的演员合并
2. 记录每个分量的演员集合
3. 按时间顺序处理每一幕，更新连通分量和集合
4. 当某个分量满足确定条件时，记录该幕编号作为分量中所有演员的答案

具体实现

数据结构

vector<int> parent;  // 并查集父节点
vector<set<int>> components;  // 每个分量的演员集合
vector<int> answer;  // 每个演员的答案

算法步骤

1. 初始化并查集，每个演员独立一个分量
2. 对于第 $i$ 幕（$i$ 从 1 到 $M$）：
   • 读取该幕的演员列表
   • 将这些演员两两合并（使用并查集）
   • 更新合并后分量的演员集合
   • 检查是否有分量满足确定条件：
     • 如果分量大小等于该分量中不同演员的数量
     • 且该分量的演员还没有被确定
     • 则记录当前幕数作为这些演员的答案

复杂度分析

• 时间复杂度：$O(\alpha(N) \cdot \sum K_i)$，其中 $\alpha$ 是阿克曼反函数
• 空间复杂度：$O(N + \sum K_i)$

代码实现

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct DSU {
    vector<int> parent;
    vector<int> size;
    
    DSU(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y]) {
                swap(x, y);
            }
            parent[y] = x;
            size[x] += size[y];
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    DSU dsu(N);
    vector<set<int>> components(N + 1);
    vector<int> answer(N + 1, 0);
    
    // 初始化每个分量的集合
    for (int i = 1; i <= N; i++) {
        components[i].insert(i);
    }
    
    for (int scene = 1; scene <= M; scene++) {
        int K;
        cin >> K;
        vector<int> actors(K);
        for (int j = 0; j < K; j++) {
            cin >> actors[j];
        }
        
        // 合并同一幕中的演员
        for (int j = 1; j < K; j++) {
            int u = actors[0];
            int v = actors[j];
            int root_u = dsu.find(u);
            int root_v = dsu.find(v);
            
            if (root_u != root_v) {
                // 合并两个分量
                if (dsu.size[root_u] < dsu.size[root_v]) {
                    swap(root_u, root_v);
                }
                
                // 将小集合合并到大集合
                for (int actor : components[root_v]) {
                    components[root_u].insert(actor);
                }
                components[root_v].clear();
                dsu.unite(u, v);
            }
        }
        
        // 更新所有出现在这一幕中的演员所在的分量
        set<int> roots_updated;
        for (int actor : actors) {
            int root = dsu.find(actor);
            roots_updated.insert(root);
        }
        
        // 检查哪些分量可以确定
        for (int root : roots_updated) {
            if (answer[root] == 0 && components[root].size() == dsu.size[root]) {
                answer[root] = scene;
                // 标记该分量中所有演员
                for (int actor : components[root]) {
                    answer[actor] = scene;
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= N; i++) {
        cout << answer[i] << (i == N ? "\n" : " ");
    }
    
    return 0;
}