M02186: Popular Cows

SCC, http://cs101.openjudge.cn/practice/02186/

理由：经典的 SCC 应用。题意是寻找被所有牛崇拜的牛。通过缩点后观察出度为 0 的点。

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

输入

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

输出

* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

样例输入

样例输出

提示

Cow 3 is the only cow of high popularity.

来源

USACO 2003 Fall

这道题是强连通分量（SCC）的经典应用题。理解这道题的关键在于将“抽象的崇拜关系”转化为“图论的连通性”，并通过“缩点”简化问题。

核心解题思路

崇拜的传递性：如果 A 崇拜 B，B 崇拜 C，那么 A 崇拜 C。这说明如果图中存在一条从 A 到 B 的路径，则 A 崇拜 B。
SCC 的性质：在一个强连通分量内部，任何两个点都可以互相到达。也就是说，同一个 SCC 里的所有牛都是互相崇拜的。
缩点与 DAG（有向无环图）：我们将每个 SCC 缩成一个点。缩点后的图是一个 DAG。
寻找被所有人崇拜的牛：
- 在缩点后的 DAG 中，如果一个点的出度为 0，说明这个点（SCC）里的牛不再崇拜其他 SCC 里的牛了。
- 如果 恰好只有一个 出度为 0 的 SCC，那么这个 SCC 里的所有牛就是被其他所有牛崇拜的。因为在 DAG 中，从任何一个点出发，最终都会流向出度为 0 的点。
- 如果 出度为 0 的 SCC 超过一个（例如有两个点 A 和 B 出度都为 0），那么 A 无法到达 B，B 也无法到达 A。这意味着没有牛能被所有人崇拜，答案为 0。

算法步骤

使用 Tarjan 算法 找到图中所有的 SCC。
统计每个 SCC 的出度（如果有一条原图边 $u \to v$ 且 $u, v$ 属于不同 SCC，则 $u$ 所在的 SCC 出度加 1）。
统计出度为 0 的 SCC 数量：
- 如果数量为 1，答案就是该 SCC 包含的牛的数量。
- 如果数量不为 1（或为 0，但在正常图中至少为 1），答案为 0。

Python 代码实现

python

import sys

# 增加递归深度
sys.setrecursionlimit(100000)

def solve():
    # 使用快读
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    adj = [[] for _ in range(n + 1)]
    edges = []
    idx = 2
    for _ in range(m):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        edges.append((u, v))
        idx += 2

    # --- Tarjan 算法变量 ---
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    stack = []
    in_stack = [False] * (n + 1)
    timer = 0
    
    scc_id = [0] * (n + 1)
    scc_size = {} # 记录每个 SCC 包含的节点数
    scc_count = 0

    def tarjan(u):
        nonlocal timer, scc_count
        timer += 1
        dfn[u] = low[u] = timer
        stack.append(u)
        in_stack[u] = True
        
        for v in adj[u]:
            if not dfn[v]:
                tarjan(v)
                low[u] = min(low[u], low[v])
            elif in_stack[v]:
                low[u] = min(low[u], dfn[v])
        
        if dfn[u] == low[u]:
            scc_count += 1
            count = 0
            while True:
                node = stack.pop()
                in_stack[node] = False
                scc_id[node] = scc_count
                count += 1
                if node == u:
                    break
            scc_size[scc_count] = count

    # 寻找 SCC
    for i in range(1, n + 1):
        if not dfn[i]:
            tarjan(i)

    # --- 统计缩点后各 SCC 的出度 ---
    out_degree = [0] * (scc_count + 1)
    for u, v in edges:
        if scc_id[u] != scc_id[v]:
            out_degree[scc_id[u]] += 1

    # --- 分析结论 ---
    zero_out_count = 0
    target_scc = 0
    
    for i in range(1, scc_count + 1):
        if out_degree[i] == 0:
            zero_out_count += 1
            target_scc = i
            
    if zero_out_count == 1:
        # 只有一个出度为 0 的 SCC，该 SCC 里的牛就是答案
        print(scc_size[target_scc])
    else:
        # 如果有多个出度为 0 的点，说明它们之间互不到达，没有牛能被所有人崇拜
        print(0)

if __name__ == "__main__":
    solve()

关键点总结：

为什么是出度为 0？ 在崇拜关系图中， $A \to B$ 表示 A 崇拜 B。信息流向是“崇拜的对象”。如果一个点（SCC）没有连向外面的边了，说明大家都崇拜它，但它不崇拜别人。如果这样的点只有一个，它就是“终点”，所有人的崇拜最终都会指向这里。
复杂度分析：
- Tarjan 算法： $O (N + M)$
- 统计出度： $O (M)$
- 总时间复杂度 $O (N + M)$ ，对于 $N = 10^{4}, M = 50^{4}$ 来说非常轻松。
注意点： Python 的递归深度限制需要手动上调。此外，若 $N$ 很大，sys.stdin.read().split() 比多次调用 input() 效率更高。

【李思朋、工院】思路：感觉强连通分量的题是要想到可以利用强连通分量以及缩点后的操作，寻找强连通还是比较套路化的，包括下一题也一样，比如这题难点在要想到被所有牛崇拜的牛一定是单点或者一个强连通分量中的所有点，在缩点之后形成的有向无环图中找到所有出度为0的点（强连通分量），结合提前记录的强连通分量各自的size从而实现本题（需要注意的是缩点后找到出度为0的点或块只有1个，否则图是不连通的）

M02186: Popular Cows ​

M02186: Popular Cows