こんにちは
graphに弱いと感じているかたは必見の良問です。
今回の学びは
・Cyclicは白、灰色、黒で訪問状態を管理する
・visitedまで行けば終端ありでcyclicでない。と変数を圧縮というか、visitedでそれだけ表現できる、と気づくとコーディングが楽になる.
・配列でといて、さらにパフォーマンス、さらにすぺーすを改善するにはhashmapを使うことである。あらためてhashmapは偉大である。
エッジは一回しか通らず、だから結果的にO(V + E)となる。
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
O(V * E) , Vがノード数でEがエッジ数
と答えたけど、これは間違い！
https://leetcode.com/articles/find-eventual-safe-states/ ほらここに書いてあるし、
というのはvisitedでまだ終わってないノードのエッジだけたどる
のでエッジは一回しか通らず、だから結果的にO(V + E)となる。
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
サイクリックかどうかをhashmapでvisitedをとって、visitedまで行けば非サイクリックだよ。
Detect Cycle in Directed Graph Algorithmの動画
で、Cyclicは白、灰色、黒で訪問状態を管理する、基本を教えてくれています。
で、このヒントを元に、作ったバージョンは動くのですがLTEでました。。。。
# let's improve Solution_working_but_LTE
class Solution():
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
def is_cyclic(i):
# 0 1 2 3 4 5 6
# 0, [[1,2],[2,3],[5],[0],[5],[],[]]
G = set(); B = set()
def dfs(i): # 1 -> 2 -> 5
if i in memo: return memo[i]
# G: [0, 1, 2]
# B: [5]
if i in G:
return True
G.add(i)
for next_i in graph[i]: # 1, 2 -> 2, 3
if next_i not in B:
if dfs(next_i): return True
G.remove(i)
B.add(i)
ans = dfs(i)
memo[i] = ans
return ans == True
A = []
memo = {}
for i in range(len(graph)):
if not is_cyclic(i):
A.append(i)
return A
でもそれでもできなかったので写経しました。
こちら参考にさせていただきました。https://leetcode.com/problems/find-eventual-safe-states/discuss/444740/classic-topological-sort-using-dfs
class Solution():
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
N = len(graph)
if N == 0: return []
A = []
visited = defaultdict(int)
for i in range(N):
if self.dfs(graph, i, visited):
A.append(i)
return A
def dfs(self, graph, i, visited):
if visited[i] == 2: return True
if visited[i] == 1: return False
visited[i] = 1
for j in graph[i]:
if self.dfs(graph, j, visited) == False: return False
visited[i] = 2
return True
デバッグでうごかして初めて分かりました。
cyclickを各ノードからスタートして確認していく。一回、検索すると
visiting:1という状態で終わるノードがでてくる。これらは、一回すでに調べてた上でvistingなのでcyclicという意味だ。
逆にvisited:2という状態まですすんだノードっていうのは、終端あり（cyclicでない)ということになる。
これがvisitedを使い回せば勝手に、これまでの結果を引き続き使ってくれることになる。
最初のLTEの考え方と同じだけど、
visitedまで行けば終端ありでcyclicでない。と変数を圧縮というか、visitedでそれだけ表現できる、と気づくとコーディングが楽になる
これがポイントだとおもった。
また最初のLTEの作品と今回のパスするコードの違いは、visitedなどの状態をhashで持つか、配列で持つかの違いである。
配列でといて、さらにパフォーマンス、さらにすぺーすを改善するにはhashmapを使うことである。あらためてhashmapは偉大である。
実はこの人の実装も同じく配列のせいでLTEになっていると思うよ。
まとめ
・Cyclicは白、灰色、黒で訪問状態を管理する
・visitedまで行けば終端ありでcyclicでない。と変数を圧縮というか、visitedでそれだけ表現できる、と気づくとコーディングが楽になる.
・配列でといて、さらにパフォーマンス、さらにすぺーすを改善するにはhashmapを使うことである。あらためてhashmapは偉大である。
・エッジは一回しか通らず、だから結果的にO(V + E)となる。
以上です