785.md

Is Graph Bipartite?

Description

link

---

Solution

• See Code

---

Code

最坏情况：O(n^2)

class Solution:
    '''
    描边，使用字典记录所有index的情况，dfs当中处理
    '''
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = {}
        def dfs(pos):
            for i in graph[pos]:
                if i in color:
                    if color[i] == color[pos]:
                        return False
                else:
                    color[i] = 1 - color[pos]
                    if not dfs(i):
                        return False
            return True
        for i in range(len(graph)):
            if i not in color:
                color[i] = 0
                if not dfs(i):
                    return False
        return True