二分图判定

图

说明

相邻顶点染不同颜色；冲突表示图不能分成两个独立集合。

分析

对每个未染色连通分量，从任意顶点赋一种颜色，并让所有邻居取相反颜色。若一条边连接同色两点，就不可能把图分成两个内部无边的集合。

图解推演

链 0—1—2 可以染成红、蓝、红。同一连通分量内颜色可整体翻转，不影响结论。若再连 2—0，三角形会要求两个红点相邻，产生矛盾；只从一个起点染色会漏掉其他分量中的奇环。

查看图表代码

适用前提与边界

奇数长度环会导致这样的冲突。

示例输入与调用

fmt.Println(IsBipartite([][]int{{1}, {0, 2}, {1}}))

运行输出

true

完整 Go 示例

package main

import "fmt"

func IsBipartite(g [][]int) bool {
	color := make([]int, len(g))
	for s := range g {
		if color[s] != 0 {
			continue
		}
		color[s] = 1
		q := []int{s}
		for h := 0; h < len(q); h++ {
			v := q[h]
			for _, w := range g[v] {
				if color[w] == color[v] {
					return false
				}
				if color[w] == 0 {
					color[w] = -color[v]
					q = append(q, w)
				}
			}
		}
	}
	return true
}

func main() {
	fmt.Println(IsBipartite([][]int{{1}, {0, 2}, {1}}))
}