785. 判断二分图

题目：

给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合
，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。
每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边：
graph[i] 中不存在i，并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-graph-bipartite
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

10min

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for _ in range(n)]
        self.count = n
    def find(self,p):
        while self.parent[p] != self.parent[self.parent[p]]:
            self.parent[p] = self.parent[self.parent[p]]
        return self.parent[p]
    def union(self,p,q):
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        if self.rank [i] < self.rank [j]:
            self.parent[i] = j
            self.rank [j] += self.rank [i]
        else:
            self.parent[j] = i
            self.rank [i] += self.rank [j]
        self.count -= 1
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if not graph:return True
        n=len(graph)
        work= UnionFind(n)
        for j,node in enumerate(graph):
            m=len(node)
            if m==1:continue
            for i in range(1,m):
                work.union(node[i-1],node[i])
            for neighbour in node:
                if work.find(j)==work.find(neighbour):
                    return False
        return True

要点：

1. 套用并查集模板

2. 二分图定义：

定义：一条边的两段属于两个集合
即一个点和他的邻居必然是两个集合

3. 算法过程：

遍历每个点的邻居集合，首先union他的所有邻居，再做一遍发现他的邻居和他是一个爹，就false

其他：

代码报错：无