Amazing Whispers 题解

题目分析

这是一个关于信息传递路径和替换检测的图论问题。游戏规则如下：

• 有 $N \times M$ 个人，分成 $M$ 组，每组 $N$ 人
• 信息从组1传递到组M，每组内部形成完美匹配
• 只有一条信息被替换成粗鲁的话
• A持有丢失的原始信息，B读出粗鲁话
• 需要找出所有可能进行信息替换的人

解题思路

核心观察

替换点必须满足两个条件：

1. 可达性条件：存在从A到替换点的路径（原始信息传递）
2. 连通性条件：存在从替换点到B的路径（粗鲁信息传递）

算法设计

使用双向BFS搜索：

• 正向BFS：从A出发，找到所有可达节点
• 反向BFS：从B出发反向搜索，找到所有能到达B的节点
• 交集：两者的交集就是可能的替换点

复杂度分析

• 时间复杂度：$O(N \times M + E)$，其中E是总边数
• 空间复杂度：$O(N \times M)$

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 20
#define MAX_M 1000
#define MAX_NODES (MAX_N * MAX_M)

int n, m, A, B;
int edges[MAX_NODES][MAX_N + 1];  // 邻接表，edges[i][0]存储出边数量
int reachable_from_A[MAX_NODES];  // 从A可达的节点标记
int reachable_to_B[MAX_NODES];    // 能到达B的节点标记

// 正向BFS：从start出发找到所有可达节点
void bfs_from(int start, int* reachable) {
    int queue[MAX_NODES];
    int front = 0, rear = 0;
    
    // 初始化可达性数组
    memset(reachable, 0, sizeof(int) * MAX_NODES);
    reachable[start] = 1;
    queue[rear++] = start;
    
    // BFS遍历
    while (front < rear) {
        int u = queue[front++];
        // 遍历u的所有出边
        for (int i = 1; i <= edges[u][0]; i++) {
            int v = edges[u][i];
            if (!reachable[v]) {
                reachable[v] = 1;
                queue[rear++] = v;
            }
        }
    }
}

// 反向BFS：找到所有能到达target的节点
void reverse_bfs_to(int target, int* reachable) {
    int queue[MAX_NODES];
    int front = 0, rear = 0;
    
    // 初始化可达性数组
    memset(reachable, 0, sizeof(int) * MAX_NODES);
    reachable[target] = 1;
    queue[rear++] = target;
    
    // 反向BFS遍历
    while (front < rear) {
        int u = queue[front++];
        // 遍历所有可能的入边
        for (int prev = 0; prev < n * (m - 1); prev++) {
            // 检查prev是否有边指向u
            for (int i = 1; i <= edges[prev][0]; i++) {
                if (edges[prev][i] == u && !reachable[prev]) {
                    reachable[prev] = 1;
                    queue[rear++] = prev;
                }
            }
        }
    }
}

int main() {
    // 读取输入参数
    scanf("%d %d %d %d", &n, &m, &A, &B);
    
    // 初始化邻接表
    for (int i = 0; i < n * (m - 1); i++) {
        edges[i][0] = 0;
    }
    
    // 读取边信息
    for (int i = 0; i < n * (m - 1); i++) {
        int k;
        scanf("%d", &k);
        edges[i][0] = k;
        for (int j = 1; j <= k; j++) {
            scanf("%d", &edges[i][j]);
        }
    }
    
    // 步骤1：正向BFS，找到从A可达的所有节点
    bfs_from(A, reachable_from_A);
    
    // 步骤2：反向BFS，找到所有能到达B的节点
    reverse_bfs_to(B, reachable_to_B);
    
    // 步骤3：找出满足条件的替换点
    int result[MAX_NODES];
    int count = 0;
    
    for (int culprit = 0; culprit < n * m; culprit++) {
        // 排除A本身（A持有原始信息）
        if (culprit == A) continue;
        
        // 检查是否同时满足两个条件
        if (reachable_from_A[culprit] && reachable_to_B[culprit]) {
            result[count++] = culprit;
        }
    }
    
    // 输出结果
    printf("%d\n", count);
    for (int i = 0; i < count; i++) {
        printf("%d\n", result[i]);
    }
    
    return 0;
}

关键点说明

1. 图结构建模

• 使用邻接表存储假装传话的关系
• 节点编号从0到$N \times M - 1$
• 每组包含连续的N个节点

2. 双向搜索策略

• 正向BFS：模拟原始信息的传播路径
• 反向BFS：模拟粗鲁信息的来源追溯
• 两者的交集确保替换点在关键路径上

3. 边界条件处理

• 排除A本身作为替换点
• 正确处理节点编号和组别的关系
• 处理大规模数据时的内存管理

算法正确性证明

设C为替换点，则：

1. 必要性：如果C是替换点，那么必须存在A→C和C→B的路径
2. 充分性：由于题目保证输入有效，存在A→C和C→B的路径意味着可以构造相应的匹配

因此，算法找到的所有节点都是可能的替换点。

样例验证

样例1

输入：
2 3 1 5
1 3
1 2
2 5 4
2 4 5
输出：
3
1
2
5

样例2

输入：
3 3 0 6
1 4
1 5
1 3
1 7
2 6 7
1 8
输出：
3
0
4
6

该解法充分利用了图的可达性特性，通过高效的双向搜索在合理时间内解决问题，适用于题目给定的数据范围。