Solve

判定给定图是否为二分图

题目描述请参考 LeetCode - 785

分析

二分图的充要条件是：任何一个结点回路的长度为偶数。

所以我们如果将定义实现就是一个正确的方法了。但是有个问题，这样需要穷举判定全部的回路，时间复杂度过高。
简单办法（参考引申）：任选一个结点开始进行黑白交叉染色，起点开始奇数距离路径的结点全部都跟自己异色，偶数则同色。否则必然不是二分图，这一点也与定义一致，考虑到全部偶数距离的路径也包括回路，所以必是同色。因此当我们染色发生矛盾时就能知道这张图就不是二分图了。

*引申：任选一个结点a放入A集合，若给定图是二分图，则所有到a路径长度为偶数的结点均可放入A集合，否则均可放入A’集合，A与A’构成二分图。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        size = len(graph)
        if not graph:
            return False
        
        edge, que, color, has = [[0 for _ in range(size)] for _ in range(size)], [], [0] * size, []

        for x, i in enumerate(graph):
            for y in i:
                edge[x][y] = edge[y][x] = 1
        
        for i in range(0, size):
            
            if color[i] == 0:
                que.append(i)
                color[i] = 1
            
                while que:
                    curr = que.pop()
                    has.append(curr)
            
                    for i in range(0, size):
                        if edge[curr][i]:
                            if color[i] == 0:
                                color[i] = -color[curr]
                            elif color[i] == color[curr]:
                                return False                    
                            if i not in has:
                                que.append(i)     
        return True