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