09202: 舰队、海域出击！

Topological Order, http://cs101.openjudge.cn/practice/09202/

作为一名海军提督，Pachi将指挥一支舰队向既定海域出击！ Pachi已经得到了海域的地图，地图上标识了一些既定目标和它们之间的一些单向航线。如果我们把既定目标看作点、航线看作边，那么海域就是一张有向图。不幸的是，Pachi是一个会迷路的提督QAQ，所以他在包含环(圈)的海域中必须小心谨慎，而在无环的海域中则可以大展身手。受限于战时的消息传递方式，海域的地图只能以若干整数构成的数据的形式给出。作为舰队的通讯员，在出击之前，请你告诉提督海域中是否包含环。

例如下面这个海域就是无环的：

而下面这个海域则是有环的（C-E-G-D-C）：

输入

每个测试点包含多组数据，每组数据代表一片海域，各组数据之间无关。第一行是数据组数T。每组数据的第一行两个整数N，M，表示海域中既定目标数、航线数。接下来M行每行2个不相等的整数x,y，表示从既定目标x到y有一条单向航线（所有既定目标使用1~N的整数表示）。描述中的图片仅供参考，其顶点标记方式与本题数据无关。

1<=N<=100000，1<=M<=500000，1<=T<=5 注意：输入的有向图不一定是连通的。

输出

输出包含T行。对于每组数据，输出Yes表示海域有环，输出No表示无环。

样例输入

样例输出

No
Yes

提示

输入中的两张图就是描述中给出的示例图片。

拓扑排序检查有向图是否存在环

python

# 蒋子轩 工院
from collections import deque,defaultdict
def topo_sort(graph):
    in_degree={u:0 for u in range(1,n+1)}
    for u in graph:
        for v in graph[u]:
            in_degree[v]+=1
    q=deque([u for u in in_degree if in_degree[u]==0])
    topo_order=[]
    while q:
        u=q.popleft()
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v]-=1
            if in_degree[v]==0:
                q.append(v)
    if len(topo_order)!=len(graph):
        return 'Yes'
    return 'No'
for _ in range(int(input())):
    n,m=map(int,input().split())
    graph=defaultdict(list)
    for _ in range(m):
        u,v=map(int,input().split())
        graph[u].append(v)
    print(topo_sort(graph))

可以dfs完成对一个节点的所有邻居的访问后，将这个节点标记为已完全访问（color[node] = 2）。这意味着我们已经探索了从这个节点出发可以到达的所有节点，而且没有发现环。

python

from collections import defaultdict

def dfs(node, color):
    color[node] = 1
    for neighbour in graph[node]:
        if color[neighbour] == 1:
            return True
        if color[neighbour] == 0 and dfs(neighbour, color):
            return True
    color[node] = 2
    return False

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)
    color = [0] * (N + 1)
    is_cyclic = False
    for node in range(1, N + 1):
        if color[node] == 0:
            if dfs(node, color):
                is_cyclic = True
                break
    print("Yes" if is_cyclic else "No")

拓扑排序检查有向图是否存在环。它的基本思想是通过计算每个顶点的入度，并从入度为 0 的顶点开始进行深度优先搜索（DFS）。在 DFS 过程中，每遍历到一个顶点时，将其标记为已访问，并将其所有邻居的入度减一。如果邻居的入度减为 0，则继续对邻居进行 DFS。如果最终所有顶点都被访问到，则图中不存在环；否则，存在环。

python

from collections import defaultdict

def dfs(p):
    vis[p] = True
    for q in graph[p]:
        in_degree[q] -= 1
        if in_degree[q] == 0:
            dfs(q)

for _ in range(int(input())):
    n, m = map(int, input().split())
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    vis = [False] * (n + 1) 
    for _ in range(m):
        x, y = map(int, input().split())
        graph[x].append(y)
        in_degree[y] += 1
    for k in range(1, n + 1):  
        if in_degree[k] == 0 and not vis[k]:  
            dfs(k)
    flag = any(not vis[i] for i in range(1, n + 1))  
    print('Yes' if flag else 'No')

09202: 舰队、海域出击！ ​

09202: 舰队、海域出击！