0785. Is Graph Bipartite¶
题目信息¶
- 题号:
0785
- 难度:
Medium
- 主题:
无向图、二分图、顶点分组
- 原题:
- 重点:
邻接表描述无自环、无重边的无向图,图可能不连通;需要判断能否把全部节点分成两组,使每条边的两个端点分属不同组
题目重述¶
给定一个含 n 个节点的无向图,节点编号为 0 至 n - 1。二维数组 graph 是其邻接表:若 v 出现在 graph[u] 中,则节点 u 与 v 之间存在一条无向边。
图中没有自环和重复边,邻接关系是对称的,但图可能由多个互不连通的部分组成。
若可以把所有节点划分到两个互不相交的集合中,使每条边的两个端点分别位于不同集合,则该图是二分图。请判断输入图是否为二分图。
1 <= n <= 100;每个邻接节点编号均在 [0, n - 1] 范围内,同一邻接列表中的值互不重复。
自建示例¶
不连通图的每个分量都可以二分:
输入:graph = [[1],[0],[3,4],[2],[2]]
输出:true
解释:节点 0、1 构成一个分量,节点 2、3、4 构成另一个分量。可以把节点分为 {0,2} 与 {1,3,4},所有边都连接两个不同集合。
含有五个节点组成的奇数环:
输入:graph = [[1,4],[0,2],[1,3],[2,4],[0,3]]
输出:false
解释:节点 0、1、2、3、4 依次组成长度为 5 的环。沿环交替分组后,第五条边仍会连接同组节点,因此不可能完成二分。