拓扑排序 代码实现思路:
1. 入队所有入度为0 的点
2. bfs 取出队头t 枚举t的所有出边 t->j
3. 删掉 t->j 即让 d[j]– (d[j] j的入度)
4. if d[j] == 0 -> 说明j之前所有点均以排好序 -> j 入队
5. 如果图中存在环则无法全部入队 反之则都可以入队

先看一个基础点的题
leetcode 210 原题链接:
https://leetcode.cn/problems/course-schedule-ii/
算是一道经典题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        n = numCourses

        def topSort(edges):
            # 建图
            g = [[] for _ in range(n)]
            # 存入度
            d = [0 for _ in range(n)]
            for x, y in edges:
                g[y].append(x)
                d[x] = d[x] + 1

            q = deque([i for i, v in enumerate(d) if v == 0])
            # 拓扑序
            order = []
            while q:
                x = q.popleft()
                order.append(x)
                for y in g[x]:                
                    d[y] = d[y] - 1
                    if d[y] == 0 :
                        q.append(y)
            
            return order if len(order) == n else []
            
        return topSort(prerequisites)

然后再看6163这道题
题目链接:
https://leetcode.cn/problems/build-a-matrix-with-conditions/
主要变形在最后填入矩阵那里 以及给的输入并不是从0开始需要稍作处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topSort(edges):
            # 题目给的是 1-k 所以对应范围是 1-k+1
            # 链表 存图
            g = [[] for _ in range(k + 1)]
            # 存入度
            d = [0 for i in range(k + 1)]
            for x, y in edges:
                g[x].append(y)
                d[y] = d[y] + 1

            q = deque()
            # 根据题意 不存在0这个位置
            d[0] = -1
            # 将入度为0的先入队
            for i, v in enumerate(d):
                if v == 0:
                    q.append(i)

            order = []

            while q:
                t = q.popleft()
                order.append(t)
                for y in g[t]:
                    d[y] = d[y] - 1
                    if d[y] == 0:
                        q.append(y)
            if len(order) < k:
                return []

            return list(order)

        row = topSort(rowConditions)
        if not row:
            return []
        col = topSort(colConditions)
        if not col:
            return []

        # 建立 列与其出现顺序的映射
        pos = {x: i for i, x in enumerate(col)}

        ans = [[0] * k for _ in range(k)]

        # 按这个顺序遍历 x 一定是符合行的条件的 
        # 然后通过pos[x] 找到对应列符合条件的位置 填入值即可完成构造
        for i, x in enumerate(row):
            ans[i][pos[x]] = x

        return ans