题解 | #学习资料#

题目链接

学习资料

题目描述

总共有 $N$ 个营员，编号为 $1, \dots, N$ 。每个营员 $i$ 都填写了一份调查表，指明他愿意将资料拷贝给哪些其他营员。

资料的传递是具有传递性的：如果营员 $A$ 愿意给 $B$ ， $B$ 又愿意给 $C$ ，那么一旦 $A$ 获得了资料， $B$ 和 $C$ 最终也都能获得资料。

现在需要确定，至少要刻录多少张光盘（即初始发给多少个营员），才能保证所有 $N$ 个营员最终都能得到资料。

解题思路

这是一个关于有向图中信息传递和覆盖的问题。我们可以将问题抽象为一个图论模型来求解。

1. 图的构建

将 $N$ 个营员视为图中的 $N$ 个顶点。
如果营员 $i$ 愿意将资料拷贝给营员 $j$ ，我们就在图中画一条从 $i$ 指向 $j$ 的有向边 $(i \to j)$ 。
这样，我们就构建了一个代表资料传递关系的有向图。

2. 强连通分量 (SCC)

在有向图中，如果两个顶点可以相互到达，则称它们是强连通的。图中的一个极大强连通子图被称为强连通分量 (Strongly Connected Component, SCC)。

在本题中，一个 SCC 具有重要的性质：只要 SCC 内的任意一个营员获得了资料，那么该 SCC 内的所有其他营员最终也都能获得资料，因为他们之间可以相互传递。

因此，我们可以将每个 SCC “收缩”成一个超级节点。这样，原图就被转换成了一个由这些超级节点构成的有向无环图 (Directed Acyclic Graph, DAG)。

3. 求解DAG的起点

问题现在转化为了：在这个由 SCC 构成的 DAG 中，我们需要给多少个超级节点“源头”（即发放光盘），才能使得信息流能够覆盖所有的超级节点？

答案是：我们需要给所有入度为 0 的超级节点发放光盘。

一个超级节点（SCC）的入度为 0，意味着没有任何来自其他 SCC 的边指向它。因此，这个 SCC 无法从其他群体接收到资料，必须有一个初始的资料来源（光盘）。只要所有入度为 0 的 SCC 都获得了光盘，那么资料就可以沿着 DAG 的边流向所有其他 SCC，最终覆盖所有营员。

所以，题目的答案就是缩点后图中入度为 0 的 SCC 的数量。

4. 算法实现

我们可以使用 Tarjan 算法 来高效地求解 SCC。

建图：根据输入构建邻接表表示的有向图。
Tarjan 算法：对图进行深度优先搜索 (DFS)，计算每个节点的 $dfn$ (发现时间戳) 和 $low$ (能追溯到的最早祖先的时间戳)，并用一个栈来辅助。当 $dfn[u] = low[u]$ 时，就找到了一个 SCC。
统计入度：在找到所有 SCC 并为每个节点分配一个 SCC 编号后，我们遍历原图的所有边 $(u, v)$ 。如果节点 $u$ 和 $v$ 属于不同的 SCC（即 $scc\_id[u] \neq scc\_id[v]$ ），则说明在缩点后的 DAG 中，有一条从 $scc\_id[u]$ 指向 $scc\_id[v]$ 的边。此时，我们将 $scc\_id[v]$ 的入度加一。
计算结果：最后，统计所有 SCC 中入度为 0 的数量，即为最终答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<vector<int>> adj;
vector<int> dfn, low, scc_id;
vector<bool> on_stack;
stack<int> s;
int timestamp, scc_count;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    s.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_count++;
        int node;
        do {
            node = s.top();
            s.pop();
            on_stack[node] = false;
            scc_id[node] = scc_count;
        } while (node != u);
    }
}

int main() {
    int n;
    cin >> n;

    adj.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        int v;
        while (cin >> v && v != 0) {
            adj[i].push_back(v);
        }
    }

    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    on_stack.assign(n + 1, false);
    timestamp = 0;
    scc_count = 0;

    for (int i = 1; i <= n; ++i) {
        if (dfn[i] == 0) {
            tarjan(i);
        }
    }

    if (scc_count == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> in_degree(scc_count + 1, 0);
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                in_degree[scc_id[v]]++;
            }
        }
    }

    int zero_in_degree_count = 0;
    for (int i = 1; i <= scc_count; ++i) {
        if (in_degree[i] == 0) {
            zero_in_degree_count++;
        }
    }

    cout << zero_in_degree_count << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    private static List<List<Integer>> adj;
    private static int[] dfn, low, sccId;
    private static boolean[] onStack;
    private static Stack<Integer> stack;
    private static int timestamp, sccCount;

    private static void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        onStack[u] = true;

        for (int v : adj.get(u)) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            sccCount++;
            int node;
            do {
                node = stack.pop();
                onStack[node] = false;
                sccId[node] = sccCount;
            } while (node != u);
        }
    }

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

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

        for (int i = 1; i <= n; i++) {
            int v;
            while ((v = sc.nextInt()) != 0) {
                adj.get(i).add(v);
            }
        }
        
        dfn = new int[n + 1];
        low = new int[n + 1];
        sccId = new int[n + 1];
        onStack = new boolean[n + 1];
        stack = new Stack<>();
        timestamp = 0;
        sccCount = 0;

        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) {
                tarjan(i);
            }
        }

        if (sccCount == 0) {
            System.out.println(0);
            return;
        }

        int[] inDegree = new int[sccCount + 1];
        for (int u = 1; u <= n; u++) {
            for (int v : adj.get(u)) {
                if (sccId[u] != sccId[v]) {
                    inDegree[sccId[v]]++;
                }
            }
        }

        int zeroInDegreeCount = 0;
        for (int i = 1; i <= sccCount; i++) {
            if (inDegree[i] == 0) {
                zeroInDegreeCount++;
            }
        }

        System.out.println(zeroInDegreeCount);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(200005)

# 全局变量，用于Tarjan算法
adj = []
dfn, low, scc_id = [], [], []
on_stack = []
stack = []
timestamp = 0
scc_count = 0

def tarjan(u):
    global timestamp, scc_count
    timestamp += 1
    dfn[u] = low[u] = timestamp
    stack.append(u)
    on_stack[u] = True

    for v in adj[u]:
        if dfn[v] == 0:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif on_stack[v]:
            low[u] = min(low[u], dfn[v])

    if dfn[u] == low[u]:
        scc_count += 1
        while True:
            node = stack.pop()
            on_stack[node] = False
            scc_id[node] = scc_count
            if node == u:
                break

def main():
    global adj, dfn, low, scc_id, on_stack, stack, timestamp, scc_count
    
    line = sys.stdin.readline()
    if not line.strip():
        print(0)
        return

    n = int(line)
    
    adj = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        parts = list(map(int, sys.stdin.readline().split()))
        adj[i] = parts[:-1] # 最后一个元素0是终止符

    # 初始化Tarjan算法所需的数组
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    scc_id = [0] * (n + 1)
    on_stack = [False] * (n + 1)
    stack = []
    timestamp = 0
    scc_count = 0
    
    # 执行Tarjan算法
    for i in range(1, n + 1):
        if dfn[i] == 0:
            tarjan(i)

    if n == 0:
        print(0)
        return
        
    # 计算缩点后每个SCC的入度
    in_degree = [0] * (scc_count + 1)
    for u in range(1, n + 1):
        for v in adj[u]:
            if scc_id[u] != scc_id[v]:
                in_degree[scc_id[v]] += 1
    
    # 统计入度为0的SCC数量
    zero_in_degree_count = 0
    for i in range(1, scc_count + 1):
        if in_degree[i] == 0:
            zero_in_degree_count += 1
            
    print(zero_in_degree_count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：Tarjan 算法求强连通分量 (SCC) + 拓扑图入度统计
时间复杂度： $\mathcal{O}(N + E)$ ，其中 $N$ 是营员数（顶点数）， $E$ 是所有愿意分享关系的总数（边数）。Tarjan 算法和后续的入度统计都只需要遍历一次所有的顶点和边。
空间复杂度： $\mathcal{O}(N + E)$ ，用于存储图的邻接表以及 Tarjan 算法所需的辅助数组。