本文共 2336 字，大约阅读时间需要 7 分钟。

题目大意是给定一群牛，其中每头牛都会给其他牛点赞。点赞关系具有传递性，即如果A点赞了B，B点赞了C，那么A也会点赞C。我们需要找出被所有牛点赞的牛的数量。

分析过程

解决思路

• 构建图结构：使用邻接表存储每个节点的出边。
• Tarjan算法：计算每个节点的低点（low point）和深度优先序数（DFN）。通过比较DFN和低点来判断节点是否是根节点。
• 统计根节点数量：如果只有一个根节点，则所有牛都指向它；否则，没有满足条件的牛。

解决代码

import sys
sys.setrecursionlimit(1 << 25)
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx +=1
    in_degree = [0]*(N+1)
    out_edges = [[] for _ in range(N+1)]
    for _ in range(M):
        A = int(data[idx])
        idx +=1
        B = int(data[idx])
        idx +=1
        out_edges[A].append(B)
        in_degree[B] +=1
    visited = [False]*(N+1)
    low = [0]*(N+1)
    dfn = [0]*(N+1)
    stack = []
    on_stack = [False]*(N+1)
    belong = [0]*(N+1)
    out = [0]*(N+1)
    Bcnt = 0
    Dindex = 0
    def tarjan(u):
        nonlocal Dindex
        dfn[u] = low[u] = Dindex
        Dindex +=1
        stack.append(u)
        on_stack[u] = True
        for v in out_edges[u]:
            if not visited[v]:
                visited[v] = True
                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]:
            Bcnt +=1
            while True:
                w = stack.pop()
                on_stack[w] = False
                belong[w] = Bcnt
                if w == u:
                    break
    for u in range(1, N+1):
        if not visited[u]:
            tarjan(u)
    for u in range(1, N+1):
        for v in out_edges[u]:
            if belong[u] != belong[v]:
                out[belong[u]] +=1
    root_count = 0
    root = 0
    for u in range(1, Bcnt+1):
        if out[u] == 0:
            root_count +=1
            root = u
    if root_count == 1:
        print(root)
    else:
        print(0)
if __name__ == "__main__":
    main()

代码解释

该方法通过Tarjan算法高效地处理了大规模图数据，确保了算法的正确性和性能。

转载地址：http://yyxfk.baihongyu.com/