首页 > 试题广场 >

二分图判定

[编程题]二分图判定

热度指数：1856 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由n个点，m条边组成的无向图（注意，此图可能不连通），对任意1 ≤ i ≤ m存在一条边连接u[i], v[i]。回答此图是不是二分图。二分图定义为存在一种给图中每一个点染上黑白两色其中之一的着色方式，使得对每一对有边直接相连的点颜色不同。

输入描述:

第一行输入为N和M，代表无向图的点数和边数。

接下来M行，表示M条边，每一行两个整数u[i], v[i]，满足1 ≤ u[i], v[i] ≤ n，保证图中无重边，自环。

其中保证1 ≤ N, M ≤ 100000

输出描述:

一行字符串，为Yes，或者No。

Yes表示输入图是二分图。

No表示输入图不是二分图。

示例1

输入

输出

Yes

说明


如图，把1， 3， 5点染色为白，2， 4染色为黑，即可满足二分图要求，所以这个图是二分图。

示例2

输入

输出

No

说明

1， 2， 3号点无论如何染色都无法满足要求，所以不是二分图。

算法知识视频讲解

白伟仝

发表于 2020-05-12 20:40:52

import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.ne 展开全文

牛客题解官

发表于 2020-06-05 16:40:48

题解题目难度：中等难度知识点：图、邻接矩阵、DFS DFS方法思路：步骤一：构造邻接邻接矩阵G[N] 示例一点连接情况的输入：1 22 33 44 14 55 2其G[N]为：步骤二：用color[N]表示点的着色情况，例如点2，color[2]=0表示点2未着色，color[2]=1表示点展开全文