アルゴリズム

【アルゴリズム脳トレ】leetcode medium 785 Is Graph Bipartite

投稿日:

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題は。。。

(時間配分は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 log (V)), pO( V )

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

 

4、実装しましょう。

最初の間違った実装は。ロジックが定まってないので、ヒューリスティックに届かないノードは全部マークしてしまっています。これでも半分くらいテスト通るので面白い。

class unionfind:
def __init__(self, n):
self.n = n
self.pars = [-1] * n
def find(self, x):
if self.pars[x] < 0:
return x
else:
oya = self.pars[x]
return self.find(oya)
#self.pars[x] = self.find(oya)
#return self.pars[x]
def union(self, x, y):
X = self.find(x)
Y = self.find(y)
if X == Y: return
if self.pars[X] > self.pars[Y]:
X, Y = Y, X
self.pars[X] += self.pars[Y]
self.pars[Y] = X
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
if graph is None: return False
N = len(graph)
if N <= 1: return False
uf = unionfind(N)
#print(uf.pars)
whole = {i for i in range(N)}
for i in range(N):
for j in whole - set(graph[i] + [i]):
uf.union(i, j)
#print(uf.pars)
return len([x for x in uf.pars if x < 0]) == 2
class unionfind: def __init__(self, n): self.n = n self.pars = [-1] * n def find(self, x): if self.pars[x] < 0: return x else: oya = self.pars[x] return self.find(oya) #self.pars[x] = self.find(oya) #return self.pars[x] def union(self, x, y): X = self.find(x) Y = self.find(y) if X == Y: return if self.pars[X] > self.pars[Y]: X, Y = Y, X self.pars[X] += self.pars[Y] self.pars[Y] = X class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: if graph is None: return False N = len(graph) if N <= 1: return False uf = unionfind(N) #print(uf.pars) whole = {i for i in range(N)} for i in range(N): for j in whole - set(graph[i] + [i]): uf.union(i, j) #print(uf.pars) return len([x for x in uf.pars if x < 0]) == 2
class unionfind:
    def __init__(self, n):
        self.n = n
        self.pars = [-1] * n
    def find(self, x):
        if self.pars[x] < 0:
            return x
        else:
            oya = self.pars[x]
            return self.find(oya)
            #self.pars[x] = self.find(oya)
            #return self.pars[x]
    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        if X == Y: return
        if self.pars[X] > self.pars[Y]:
            X, Y = Y, X

        self.pars[X] += self.pars[Y]
        self.pars[Y] = X


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if graph is None: return False
        N = len(graph)
        if N <= 1: return False
        uf = unionfind(N)
        #print(uf.pars)
        whole = {i for i in range(N)}
        for i in range(N):
            for j in whole - set(graph[i] + [i]):
                uf.union(i, j)
        #print(uf.pars)
        return len([x for x in uf.pars if x < 0]) == 2

わからなかったのでこちら、

https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution

参考にしまして、

 

class unionfind:
def __init__(self, n):
self.n = n
self.pars = [-1] * n
def find(self, x):
if self.pars[x] < 0:
return x
else:
oya = self.pars[x]
return self.find(oya)
#self.pars[x] = self.find(oya)
#return self.pars[x]
def union(self, x, y):
X = self.find(x)
Y = self.find(y)
if X == Y: return
if self.pars[X] > self.pars[Y]:
X, Y = Y, X
self.pars[X] += self.pars[Y]
self.pars[Y] = X
#https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution
class Solution_unionfind:
def isBipartite(self, graph: List[List[int]]) -> bool:
if graph is None: return False
N = len(graph)
if N <= 1: return True
uf = unionfind(N)
#print(uf.pars)
whole = {i for i in range(N)}
for i in range(N):
for j in range(len(graph[i])):
if uf.find(i) == uf.find(graph[i][j]):
return False
if j > 0:
uf.union(graph[i][j], graph[i][j-1])
return True
class unionfind: def __init__(self, n): self.n = n self.pars = [-1] * n def find(self, x): if self.pars[x] < 0: return x else: oya = self.pars[x] return self.find(oya) #self.pars[x] = self.find(oya) #return self.pars[x] def union(self, x, y): X = self.find(x) Y = self.find(y) if X == Y: return if self.pars[X] > self.pars[Y]: X, Y = Y, X self.pars[X] += self.pars[Y] self.pars[Y] = X #https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution class Solution_unionfind: def isBipartite(self, graph: List[List[int]]) -> bool: if graph is None: return False N = len(graph) if N <= 1: return True uf = unionfind(N) #print(uf.pars) whole = {i for i in range(N)} for i in range(N): for j in range(len(graph[i])): if uf.find(i) == uf.find(graph[i][j]): return False if j > 0: uf.union(graph[i][j], graph[i][j-1]) return True
class unionfind:
    def __init__(self, n):
        self.n = n
        self.pars = [-1] * n
    def find(self, x):
        if self.pars[x] < 0:
            return x
        else:
            oya = self.pars[x]
            return self.find(oya)
            #self.pars[x] = self.find(oya)
            #return self.pars[x]
    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        if X == Y: return
        if self.pars[X] > self.pars[Y]:
            X, Y = Y, X

        self.pars[X] += self.pars[Y]
        self.pars[Y] = X

#https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution
class Solution_unionfind:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if graph is None: return False
        N = len(graph)
        if N <= 1: return True
        uf = unionfind(N)
        #print(uf.pars)
        whole = {i for i in range(N)}
        for i in range(N):
            for j in range(len(graph[i])):
                if uf.find(i) == uf.find(graph[i][j]):
                    return False
                if j > 0:
                    uf.union(graph[i][j], graph[i][j-1])
        return True

 

色塗りの方法は参考動画

class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# coloring
# https://www.youtube.com/watch?v=Gmp51E8HVVs
if graph is None: return False
if len(graph) <= 1: return True
colors = [0] * len(graph)
def dfs(i, color): # trying to color the node
if colors[i] != 0:
return colors[i] == color
else:
colors[i] = color
for j in graph[i]:
if dfs(j, -color) == False:
return False
return True
for i in range(len(graph)):
if colors[i] == 0 and dfs(i, 7) == False:
return False
return True
class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: # coloring # https://www.youtube.com/watch?v=Gmp51E8HVVs if graph is None: return False if len(graph) <= 1: return True colors = [0] * len(graph) def dfs(i, color): # trying to color the node if colors[i] != 0: return colors[i] == color else: colors[i] = color for j in graph[i]: if dfs(j, -color) == False: return False return True for i in range(len(graph)): if colors[i] == 0 and dfs(i, 7) == False: return False return True
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # coloring
        # https://www.youtube.com/watch?v=Gmp51E8HVVs
        if graph is None: return False
        if len(graph) <= 1: return True

        colors = [0] * len(graph)

        def dfs(i, color): # trying to color the node
            if colors[i] != 0:
                return colors[i] == color
            else:
                colors[i] = color
                for j in graph[i]:
                    if dfs(j, -color) == False:
                        return False
            return True

        for i in range(len(graph)):
            if colors[i] == 0 and dfs(i, 7) == False:
                return False
        return True

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

 

 

 

振り返り

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

色塗りだな。

 

まとめ

 

以上です

-アルゴリズム
-,

S