图论--二分图 染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围
1≤n,m≤105
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes

import java.util.*;

public class Main
{
	static int N=100005,M=2*N,n,m,idx;
	static int h[]=new int [N],e[]=new int [M],ne[]=new int [M];
	static int color[]=new int [N];
	static void add(int a,int b)
	{
		e[idx]=b;ne[idx]=h[a];h[a]=idx++;
	}
	static boolean dfs(int u,int c)
	{
		color[u]=c;
		for(int i=h[u];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(color[j]==0)
			{
				if(dfs(j,3-c)==false)return false;
			}
			else if(color[j]==c)return false;
		}
		return true;
	}
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		Arrays.setAll(h,x->-1);
		for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5719767.html