785. 判断二分图

题目描述:

存在一个 无向图 ,图中有 n 个节点。其中每个节点都有一个介于 0n - 1 之间的唯一编号。给你一个二维数组 graph ,其中 graph[u] 是一个节点数组,由节点 u 的邻接节点组成。形式上,对于 graph[u] 中的每个 v ,都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性:

  • 不存在自环( graph[u] 不包含 u)。
  • 不存在平行边( graph[u] 不包含重复值)。
  • 如果 vgraph[u] 内,那么 u 也应该在 graph[v] 内(该图是无向图)
  • 这个图可能不是连通图,也就是说两个节点 uv 之间可能不存在一条连通彼此的路径。

二分图 定义:如果能将一个图的节点集合分割成两个独立的子集 AB ,并使图中的每一条边的两个节点一个来自 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

解题分析及思路:

方法:并查集

思路:

首先需要理解什么是二分图, 二分图是一个图,它的每个节点不能与相邻的节点处于同一个集合中。

利用并查集和二分图的定义,我们可以将某个节点的相邻节点都划分到一个集合中,如果相邻节点处于同一个集合中,则说明该图不是二分图。

例如:集合:[[1,2,3],[0,2],[0,1,3],[0,2]]

  1. 首先遍历节点0,将0的相邻节点1、2、3划分为同一个连通分量,此时0的相邻节点都处于同一个连通分量中。
  2. 遍历节点1,按理说应该将0、2划分到同一个连通分量中,但是在已存在的并查集中,节点0和节点2应该处于二分图的不同集合中,但是此时,节点0和节点2处于同一个连通分量中,所以该图不是二分图。
func isBipartite(graph [][]int) bool {
	var parent = make([]int, len(graph))
	for i := 0; i < len(graph); i++ {
		parent[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	var union func(i, j int)
	union = func(i, j int) {
		parent[find(i)] = find(j)
	}
	for i := range graph {
		for j := 0; j < len(graph[i]); j++ {
			if find(i) == find(graph[i][j]) {
				return false
			}
			union(graph[i][0], graph[i][j])
		}
	}
	return true
}

复杂度:

  • 时间复杂度:O(n + m),其中n为节点数,m为边数。
  • 空间复杂度:O(n)

执行结果:

  • 执行耗时:17 ms,击败了13.64% 的Go用户
  • 内存消耗:6.4 MB,击败了31.82% 的Go用户

通过次数 95.5K 提交次数 171.5K 通过率 55.7%

Related Posts

1026. 节点与其祖先之间的最大差值

## 题目描述:给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)示例 1: ![](/img/leetcode/1026节点与其祖先之间的最大差值/tmp-tre

read more

1038. 从二叉搜索树到更大和树

## 题目描述:给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:- 节点的左子树仅包含键 小于 节点键的节点。 - 节点的右子树仅包含键 大于 节点键的节点。 - 左右子树也必须是二叉搜索树。*示例 1:***![](/img/leetcode/

read more

105. 从前序与中序遍历序列构造二叉树

## 题目描述:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1: ``` 输入: preorder = [3,9,20,15,7], inorder = [

read more

106. 从中序与后序遍历序列构造二叉树

## 题目描述:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例 1: ``` 输入:inorder = [9,3,15,20,7], postorder

read more

109. 有序链表转换二叉搜索树

## 题目描述:给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。示例 1: ``` 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9

read more

114. 二叉树展开为链表

## 题目描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1: ``` 输入:root

read more