剑指OfferII106.二分图

题目

存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。

给定一个二维数组 graph ，表示图，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。

形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

不存在自环（graph[u] 不包含 u）。

不存在平行边（graph[u] 不包含重复值）。

如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）

这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，

一个来自 B 集合，就将这个图称为二分图。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false

解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：输入：graph = [[1,3],[0,2],[1,3],[0,2]] 输出：true

解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

提示：graph.length == n

1 <= n <= 100

0 <= graph[u].length < n

0 <= graph[u][i] <= n - 1

graph[u] 不会包含 u

graph[u] 的所有值互不相同

如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

注意：本题与主站 785 题相同：

解题思路分析

1、深度优先搜索；时间复杂度O(n)，空间复杂度O(n)

var m map[int]int

func isBipartite(graph [][]int) bool {
   n := len(graph)
   m = make(map[int]int) // 分组： 0一组，1一组
   for i := 0; i < n; i++ {
      // 没有被分配过，分配到0一组
      if _, ok := m[i]; ok == false && dfs(graph, i, 0) == false {
         return false
      }
   }
   return true
}

func dfs(arr [][]int, index int, value int) bool {
   if v, ok := m[index]; ok {
      return v == value // 已经分配，查看是否同一组
   }
   m[index] = value
   for i := 0; i < len(arr[index]); i++ {
      target := arr[index][i]
      if dfs(arr, target, 1-value) == false { // 不喜欢的人，分配到对立组：1-value
         return false
      }
   }
   return true
}

2、广度优先搜索；时间复杂度O(n)，空间复杂度O(n)

func isBipartite(graph [][]int) bool {
   n := len(graph)
   m := make(map[int]int) // 分组： 0一组，1一组
   for i := 0; i < n; i++ {
      // 没有被分配过，分配到0一组
      if _, ok := m[i]; ok == true {
         continue
      }
      m[i] = 0
      queue := make([]int, 0)
      queue = append(queue, i)
      for len(queue) > 0 {
         node := queue[0]
         queue = queue[1:]
         for i := 0; i < len(graph[node]); i++ {
            target := graph[node][i]
            if _, ok := m[target]; ok == false {
               m[target] = 1 - m[node] // 相反一组
               queue = append(queue, target)
            } else if m[node] == m[target] { // 已经分配，查看是否同一组
               return false
            }
         }
      }
   }
   return true
}

3、并查集；时间复杂度O(n)，空间复杂度O(n)

func isBipartite(graph [][]int) bool {
   n := len(graph)
   fa = Init(n)
   for i := 0; i < n; i++ {
      for j := 0; j < len(graph[i]); j++ {
         target := graph[i][j]
         if find(i) == find(target) { // 和不喜欢的人在相同组，失败
            return false
         }
         union(graph[i][0], target) // 不喜欢的人在同一组
      }
   }
   return true
}

var fa []int

// 初始化
func Init(n int) []int {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      arr[i] = i
   }
   return arr
}

// 查询
func find(x int) int {
   for x != fa[x] {
      fa[x] = fa[fa[x]]
      x = fa[x]
   }
   return x
}

// 合并
func union(i, j int) {
   fa[find(i)] = find(j)
}