题目链接

流言终结者

题目描述

在一个小镇有 个人和 对朋友关系。朋友关系是相互的。 人分为两类：

  1. 传播者：听到流言后，会告诉所有没听过的朋友。
  2. 终结者：听到流言后，不会告诉任何人。

现在有 次独立的事件，每次事件都是某个人最先听到流言。请问每次事件最终有多少人会听到流言？

解题思路

这是一个图论问题，可以将人看作节点，朋友关系看作边。流言的传播过程可以看作是在图上的一种遍历。

  • 传播者 (类型1)：当一个传播者节点被访问到，它会将信息传递给它所有的邻居节点。如果邻居节点也是传播者，那么传播会继续下去。
  • 终结者 (类型2)：当一个终结者节点被访问到，它自身接收了信息，但传播链到此为止。

由于查询次数 很多，对每次查询都进行一次完整的图遍历（如BFS/DFS）会导致超时。因此，我们需要采用一种预处理的方法。

核心思想是，流言的传播主要是在由传播者构成的连通块中进行的。一旦流言进入一个由传播者组成的连通块，它将传遍这个连通块中的所有成员。然后，这个连通块中的所有成员会把流言告诉他们各自的朋友。

基于这个思想，我们的算法分为三步：

  1. 寻找传播者连通块：

    • 我们只考虑所有类型为1（传播者）的节点以及它们之间的边，构成一个子图。
    • 使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 找到这个子图中的所有连通块。
    • 我们可以用一个数组 component_id 来记录每个传播者属于哪个连通块。

  2. 计算每个连通块的影响范围：

    • 对于每一个找到的传播者连通块，我们需要计算出如果流言从这个块内开始，最终会影响到多少人。
    • 这个影响范围包括： a. 连通块内所有的传播者自己。 b. 所有与该连通块内成员直接相连的节点（无论是传播者还是终结者）。
    • 我们可以遍历连通块中的每个成员，将他们自己以及他们的所有朋友（在原图中）加入一个 set 中，以自动去重。set 的最终大小就是这个连通块的影响范围。
    • 将计算出的影响范围大小存储起来，与连通块的ID关联。

  3. 处理查询：

    • 对于每次查询，给定一个初始听到流言的人 s。
    • 如果 s 是一个终结者（类型2），那么只有他自己会听到流言，答案是 。
    • 如果 s 是一个传播者（类型1），我们查出他所属的连通块ID，然后直接从预处理的结果中取出该连通块的影响范围大小作为答案。

通过这种预处理，每次查询的时间复杂度可以降到 。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;

    // 邻接表存图
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> types(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> types[i];
    }

    vector<int> component_id(n + 1, 0);
    map<int, vector<int>> components;
    int current_comp_id = 0;

    // 1. 使用BFS寻找所有由传播者构成的连通块
    for (int i = 1; i <= n; ++i) {
        if (types[i] == 1 && component_id[i] == 0) {
            current_comp_id++;
            queue<int> bq;
            bq.push(i);
            component_id[i] = current_comp_id;
            
            while (!bq.empty()) {
                int u = bq.front();
                bq.pop();
                components[current_comp_id].push_back(u);

                for (int v : adj[u]) {
                    if (types[v] == 1 && component_id[v] == 0) {
                        component_id[v] = current_comp_id;
                        bq.push(v);
                    }
                }
            }
        }
    }

    // 2. 预处理计算每个连通块的最终影响人数
    map<int, int> final_size;
    for (auto const& [id, members] : components) {
        set<int> affected_people;
        for (int u : members) {
            affected_people.insert(u);
            for (int v : adj[u]) {
                affected_people.insert(v);
            }
        }
        final_size[id] = affected_people.size();
    }
    
    // 3. O(1) 回答每个查询
    for (int i = 0; i < q; ++i) {
        int start_node;
        cin >> start_node;
        if (types[start_node] == 2) {
            cout << 1 << "\n";
        } else {
            cout << final_size[component_id[start_node]] << "\n";
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int[] types = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            types[i] = sc.nextInt();
        }

        int[] componentId = new int[n + 1];
        Map<Integer, List<Integer>> components = new HashMap<>();
        int currentCompId = 0;

        // 1. 寻找传播者连通块
        for (int i = 1; i <= n; i++) {
            if (types[i] == 1 && componentId[i] == 0) {
                currentCompId++;
                Queue<Integer> bq = new LinkedList<>();
                bq.add(i);
                componentId[i] = currentCompId;
                
                List<Integer> currentMembers = new ArrayList<>();
                components.put(currentCompId, currentMembers);

                while (!bq.isEmpty()) {
                    int u = bq.poll();
                    currentMembers.add(u);

                    for (int v : adj.get(u)) {
                        if (types[v] == 1 && componentId[v] == 0) {
                            componentId[v] = currentCompId;
                            bq.add(v);
                        }
                    }
                }
            }
        }

        // 2. 计算每个连通块的影响范围
        Map<Integer, Integer> finalSize = new HashMap<>();
        for (Map.Entry<Integer, List<Integer>> entry : components.entrySet()) {
            int id = entry.getKey();
            List<Integer> members = entry.getValue();
            Set<Integer> affectedPeople = new HashSet<>();
            for (int u : members) {
                affectedPeople.add(u);
                for (int v : adj.get(u)) {
                    affectedPeople.add(v);
                }
            }
            finalSize.put(id, affectedPeople.size());
        }

        // 3. 处理查询
        for (int i = 0; i < q; i++) {
            int startNode = sc.nextInt();
            if (types[startNode] == 2) {
                System.out.println(1);
            } else {
                System.out.println(finalSize.get(componentId[startNode]));
            }
        }
    }
}

from collections import deque

def main():
    # n: 人数, m: 朋友关系数, q: 事件数
    n, m, q = map(int, input().split())
    
    # 邻接表存图
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
        
    # 存储每个人的类型 (1: 传播者, 2: 终结者)
    # types[0] 留空，方便1-based索引
    types = [0] + list(map(int, input().split()))
    
    # 存储所有查询的起始者
    queries = list(map(int, input().split()))
    
    component_id = [0] * (n + 1)
    components = {}
    current_comp_id = 0
    
    # 1. 寻找传播者连通块
    for i in range(1, n + 1):
        if types[i] == 1 and component_id[i] == 0:
            current_comp_id += 1
            bq = deque([i])
            component_id[i] = current_comp_id
            
            components[current_comp_id] = []
            
            while bq:
                u = bq.popleft()
                components[current_comp_id].append(u)
                
                for v in adj[u]:
                    if types[v] == 1 and component_id[v] == 0:
                        component_id[v] = current_comp_id
                        bq.append(v)

    # 2. 计算每个连通块的影响范围
    final_size = {}
    for cid, members in components.items():
        affected_people = set()
        for u in members:
            affected_people.add(u)
            for v in adj[u]:
                affected_people.add(v)
        final_size[cid] = len(affected_people)

    # 3. 处理查询
    results = []
    for start_node in queries:
        if types[start_node] == 2:
            results.append("1")
        else:
            cid = component_id[start_node]
            # 使用 get(cid, 0) 是一个安全的做法，以防出现意外的边缘情况
            results.append(str(final_size.get(cid, 0)))
            
    print("\n".join(results))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：图论、广度优先搜索 (BFS)、预处理
  • 时间复杂度：。瓶颈在于预处理阶段：寻找连通块和计算影响范围都只需要遍历所有节点和边一次。查询阶段的时间复杂度为 。总时间复杂度为 。
  • 空间复杂度：，用于存储图的邻接表、类型数组以及连通块信息。