いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 802 find eventual safe states

投稿日:

こんにちは

graphに弱いと感じているかたは必見の良問です。

 

今回の学びは

Cyclicは白、灰色、黒で訪問状態を管理する

visitedまで行けば終端ありでcyclicでない。と変数を圧縮というか、visitedでそれだけ表現できる、と気づくとコーディングが楽になる.

配列でといて、さらにパフォーマンス、さらにすぺーすを改善するにはhashmapを使うことである。あらためてhashmapは偉大である。

エッジは一回しか通らず、だから結果的にO(V + E)となる。

問題はfind-eventual-safe-states

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

O(V * E) ,          Vがノード数でEがエッジ数

と答えたけど、これは間違い!

https://leetcode.com/articles/find-eventual-safe-states/ ほらここに書いてあるし、

というのはvisitedでまだ終わってないノードのエッジだけたどる

のでエッジは一回しか通らず、だから結果的にO(V + E)となる。

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

4、実装しましょう。

 

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

サイクリックかどうかを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)となる。

 

以上です

-アルゴリズム
-,

Copyright© CTOの日記 , 2020 All Rights Reserved.