今天來看一下拓撲排序。拓樸的重點就是建 reverse graph（反向圖），然後算反向圖的 in-degree。這個東西會等於原圖的 out-degree，在排序的過程中，如果一個點沒有任何 out-degree，表示它沒有任何連出去的邊（這個東西是會變動的，有可能這個點是終點，或者是底下的點都已經被 pop 掉），因此可以進行入列操作，也就是放到拓樸的 result array 上。然後這樣一直去檢視 queue，把 out-degree=0 的點持續 pop 掉並減掉和這個點相關的 degree，直到沒有元素為止。

802. Find Eventual Safe States 這題有兩種解法，一種是 DFS，一種是拓樸。DFS 可以從任意點開始，假如走到底都沒有環產生，就符合題目要求的 safe state。如果中間有一段產生環，則把環的部分砍掉。

拓樸解法是參考中文版的力扣官方题解（難得官方題解寫得這麼好懂），概念就是去找拓樸排序，如果能夠被排進去，表示處於 safe state。如果始終沒辦法進行入列操作，表示該點不符合拓樸的原則。所以也不用排完再篩選 answer，直接一邊排一邊放 answer 就行。

# DFS
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        vis = [0]*n
        res=[]

        def dfs(v):
            vis[v] = 1

            for u in graph[v]:
                if vis[u] == 0:
                    if not dfs(u): 
                        return False
                if vis[u] == 1: 
                    return False

            vis[v] = 2
            return True

        for i in range(len(graph)):
            if vis[i] == 0:
                dfs(i)

        for i in range(n):
            if vis[i] == 2:
                res.append(i)

        return res

# topology
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        rg = [[] for _ in graph]
        for x, ys in enumerate(graph):
            for y in ys:
                rg[y].append(x)
        in_deg = [len(ys) for ys in graph]

        q = deque([i for i, d in enumerate(in_deg) if d == 0])
        while q:
            for x in rg[q.popleft()]:
                in_deg[x] -= 1
                if in_deg[x] == 0:
                    q.append(x)

        return [i for i, d in enumerate(in_deg) if d == 0]

851. Loud and Rich 這題則是很明確的拓樸排序，值得注意的是：圖的方向以及要從哪裡入列。把 802 和 851 拿起來比就會比較有感，上一題是從底部入列，這題則是從頂部入列。

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)

        in_edge = [[] for _ in range(n)]
        out_edge = [[] for _ in range(n)]

        for bg, sm in richer:
            out_edge[bg].append(sm)
            in_edge[sm].append(bg)
        
        in_deg = [len(i) for i in in_edge]

        ans = [-1 for i in range(n)]
        ans_q = [quiet[i] for i in range(n)]

        q = [i for i in range(n) if in_deg[i] == 0]

        while q:
            i = q.pop(0)
            if ans_q[i] >= quiet[i]:
                ans_q[i] = quiet[i]
                ans[i] = i

            for j in out_edge[i]:
                if ans_q[j] > ans_q[i]:
                    ans_q[j] = ans_q[i]
                    ans[j] = ans[i]
                in_deg[j] -= 1
                if in_deg[j] == 0:
                    q.append(j)

        return ans

• topology sort
  • 802. Find Eventual Safe States
  • 851. Loud and Rich