leetcode 785 判断二分图

目录

https://leetcode-cn.com/problems/is-graph-bipartite/

判断一个图是否是二分图

这道题可以用并查集做。

题目给出了每个点相邻的点，我们只需把与一个点相邻的所有点合并，因为与同一个点相邻的所有点一定在二分图的同一侧。

最后再遍历所有点，看每个点和他相邻的点是否在同一集合。如果有在同一集合的情况就不是二分图了。

另外这个题可以用搜索的方法做，给一个点染成红色，再把它所有邻点染为蓝色，并递归下去，如果有冲突则不可行。

from typing import List
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        fa = [ -1 for i in range(len(graph)) ]
        cn = [ 1 for i in range(len(graph)) ]
        def getfa(i):
#             print(fa, i)
            if fa[i] == -1:
                return i
#             input()
            fa[i] = getfa(fa[i])
            return fa[i]
        def merge(a, b):
#             print('merge', a, b)
            faa = getfa(a)
            fab = getfa(b)
            if faa == fab:
                return
            if cn[faa] > cn[fab]:
                faa, fab = fab, faa
            fa[faa] = fab
            cn[fab] += cn[faa]
#             print(fa)
        for x in graph:
            for n in x[1:]:
                merge(x[0], n)
        s = set([getfa(i) for i in range(len(graph))])
#         print(s)
#         print(fa)
        for i in range(len(graph)):
            fai = getfa(i)
            for n in graph[i]:
                if fai == getfa(n):
                    return False
        return True