diff options
Diffstat (limited to 'eventual_safe_states.py')
-rw-r--r-- | eventual_safe_states.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/eventual_safe_states.py b/eventual_safe_states.py new file mode 100644 index 0000000..5d7d79e --- /dev/null +++ b/eventual_safe_states.py @@ -0,0 +1,43 @@ +# 802. Find Eventual Safe States +from collections import defaultdict + +""" +there is a directed graph of 'n' nodes with each node labeled from 0 to n +- 1. the graph is represented by a 0-indexed 2d integer array 'graph' where +'graph[i]' is an integer array of nodes adjacent to node 'i', meaning there +is an edge from node 'i' to each node in 'graph[i]'. a node is a terminal +node if there are no outgoing edges. a node is a safe node if every possible +path starting from that node leads to a terminal node ( or another safe +node). return an array containing all the safe nodes of the graph. the answer +should be sorted in ascending order. +""" + + +class Solution(object): + def eventualSafeNodes(self, graph): + """ + :type graph: List[List[int]] + :rtype: List[int] + """ + n = len(graph) + g = defaultdict(list) + dp = [0] * n + for i, v in enumerate(graph): + dp[i] = len(v) + for e in v: + g[e].append(i) + q = [i for i in range(n) if dp[i] == 0] + while q: + x = q.pop() + for e in g[x]: + dp[e] -= 1 + if dp[e] == 0: + q.append(e) + ans = [i for i in range(n) if dp[i] == 0] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.eventualSafeNodes(graph=[[1, 2], [2, 3], [5], [0], [5], [], []])) + print(obj.eventualSafeNodes(graph=[[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []])) |