6 拓扑排序 3题

M401: 拓扑排序

https://sunnywhy.com/sfbj/10/6/401

现有一个共n个顶点、m条边的有向无环图（假设顶点编号为从0到n-1）。输出该图的拓扑排序序列。

注：每次有多个顶点可以选择时，总是选择编号最小的那个。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

输出n个整数，表示拓扑排序序列。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

0 1 3 2

解释

对应的有向无环图如下图所示。由于每次选择编号最小的顶点，因此拓扑排序序列为0 1 3 2。

拓扑排序.png

这个问题可以使用拓扑排序算法来解决。拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点 u 到顶点 v 的路径，那么在排序中 u 一定在 v 的前面。可以使用深度优先搜索来实现拓扑排序。

以下是使用深度优先搜索实现拓扑排序的Python代码：

python

from collections import defaultdict

def topoSort(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = [i for i in range(n) if indegree[i] == 0]
    queue.sort()
    result = []

    while queue:
        u = queue.pop(0)
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
        queue.sort()

    return result

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
result = topoSort(n, edges)
print(*result)

在这段代码中，首先构建了一个图，并计算了每个顶点的入度。然后将所有入度为0的顶点添加到队列中，并对队列进行排序。然后在循环中，每次从队列中取出一个顶点，将其添加到结果中，然后遍历其所有的邻接顶点，将邻接顶点的入度减1，如果邻接顶点的入度变为0，那么就将其添加到队列中。最后，返回结果。

M402: 有向无环图的判定-拓扑排序

https://sunnywhy.com/sfbj/10/6/402

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1）。使用拓扑排序判断其是否是有向无环图，即该有向图中是否有环。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

如果是有向无环图，那么输出Yes；否则输出No。

样例1

输入

输出

Yes

解释

对应的有向图如下图所示。该图是有向无环图。

拓扑排序.png

样例2

输入

输出

No

解释

对应的有向图如下图所示。该图不是有向无环图。

有向无环图的判定-拓扑排序_样例2.png

这个问题可以通过使用拓扑排序来解决。拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点 u 到顶点 v 的路径，那么在排序中 u 一定在 v 的前面。如果在进行拓扑排序的过程中，发现存在没有被访问的顶点，但是已经没有入度为0的顶点，那么就说明图中存在环。

以下是使用拓扑排序判断有向图是否存在环的Python代码：

python

from collections import defaultdict

def isDAG(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = [i for i in range(n) if indegree[i] == 0]
    count = 0

    while queue:
        u = queue.pop(0)
        count += 1
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return count == n

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
print("Yes" if isDAG(n, edges) else "No")

在这段代码中，我们首先构建了一个图，并计算了每个顶点的入度。然后我们将所有入度为0的顶点添加到队列中。然后在循环中，我们每次从队列中取出一个顶点，然后遍历其所有的邻接顶点，将邻接顶点的入度减1，如果邻接顶点的入度变为0，那么就将其添加到队列中。最后，我们检查访问的顶点数是否等于总的顶点数，如果等于，那么说明图是有向无环图，否则说明图中存在环。

M403: 先导课程

https://sunnywhy.com/sfbj/10/6/403

现有n门课程（假设课程编号为从0到n-1），课程之间有依赖关系，即可能存在两门课程，必须学完其中一门才能学另一门。现在给出个依赖关系，问能否把所有课程都学完。

注：能同时学习多门课程时总是先学习编号最小的课程。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数、边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

如果能学完所有课程，那么输出一行Yes，然后在第二行输出学习课程编号的顺序，编号之间用空格隔开，行末不允许有多余的空格；如果不能学完所有课程，那么输出一行No，然后在第二行输出不能学习的课程门数。

样例1

输入

输出

Yes
0 1 3 2

解释

对应的依赖关系如下图所示。由于每次选择编号最小的顶点，因此学习顺序为0 1 3 2。

拓扑排序.png

样例2

输入

输出

No
3

解释

对应的依赖关系如下图所示。编号为0的课程可以直接学习；由于编号1、2、3的课程互相依赖，因此无法学习的课程数为3。

先导课程_样例2.png

这是一个 拓扑排序 问题，但有一个特殊要求：在可选课程中总是优先选择编号最小的课程。这提示我们使用 基于优先队列（最小堆）的 Kahn 算法 来实现拓扑排序。

此外，题目还要求：

如果能完成所有课程，输出 Yes 和学习顺序；
如果不能，输出 No 和 无法学习的课程数量（即不在拓扑序列中的课程数）。

python

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    
    idx = 2
    for _ in range(m):
        u = int(data[idx])
        v = int(data[idx + 1])
        idx += 2
        graph[u].append(v)
        indeg[v] += 1
    
    # 最小堆：存储当前可学的课程（入度为0）
    heap = []
    for i in range(n):
        if indeg[i] == 0:
            heapq.heappush(heap, i)
    
    topo_order = []
    
    while heap:
        u = heapq.heappop(heap)
        topo_order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    
    if len(topo_order) == n:
        print("Yes")
        print(" ".join(map(str, topo_order)))
    else:
        print("No")
        print(n - len(topo_order))

if __name__ == "__main__":
    main()

6 拓扑排序 3题 ​

M401: 拓扑排序 ​

M402: 有向无环图的判定-拓扑排序 ​

M403: 先导课程 ​

6 拓扑排序 3题

M401: 拓扑排序

M402: 有向无环图的判定-拓扑排序

M403: 先导课程