首页 > 其他分享 >860. 染色法判定二分图

860. 染色法判定二分图

时间:2024-08-12 15:27:22浏览次数:8  
标签:二分 return idx int 860 ne color 染色法

// 860. 染色法判定二分图.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/description/862/

给定一个 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
*/


#include <iostream>
#include <cstring>

using namespace std;


const int N = 100010,M=200010;
int h[N], e[M], ne[M], idx;
int n, m;
int color[N]; int cnt;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


bool dfs(int p, int c) {
	if (color[p] != 0 && color[p] != c) return false;
	if (color[p] == c) return true;

	color[p] = c; cnt++;
	for (int i = h[p]; i != -1; i = ne[i]) {
		int j = e[i];
		if ( !dfs(j, 3 - c)) {
			return false;
		}
	}

	return true;
}


int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		add(a, b); add(b, a);
	}

	for (int i = 1; i <= n; i++) {
		if (color[i] == 0) {
			if (!dfs(i, 1)) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	if (cnt == n) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

标签:二分,return,idx,int,860,ne,color,染色法
From: https://www.cnblogs.com/itdef/p/18355052

相关文章

  • 二分图判定 代码源初级
    //1001二分图判定.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。//#include<iostream>#include<memory.h>usingnamespacestd;/*http://oj.daimayuan.top/course/14/problem/797给你一张简单无向图,你需要判断这张图是否为二分图。图用以下形式给......
  • wqs二分
    wqs二分用来处理一类带有限制的问题,如恰好选\(k\)个,本质是通过二分来规避这个选取数量的限制。使用前提:原问题具有凹凸性。设\(g_i\)表示选\(i\)个物品的答案,那么所有\((i,g_i)\)点组成一个凸包,满足\(g'(k)\)单调。这类题目通常有以下特点:如果不限制选的个数,那么......
  • 黑马Java零基础视频教程精华部分_15_基本查找/顺序查找、二分查找/折半查找、插值查找
    系列文章目录文章目录系列文章目录一、基本查找/顺序查找核心思想:从0索引开始挨个往后查找代码:练习:定义一个方法利用基本查找,查询某个元素在数组中的索引,数组包含重复数据。二、二分查找/折半查找核心思想:属于有序查找算法。用给定值先与中间结点比较,每次排除一半的......
  • 模板 - 二分&三分
    二分&三分整数二分intBinarySearch(constintL,constintR){ intl=L-1,r=R+1; while(l+1<r) { intmid=l+r>>1; if(check(mid))l=mid; elser=mid; } returnl;}浮点数二分constdoubleEPS=1e-6;doubleBinarySearch(constdoubleL,constdouble......
  • 关于二分图上的最大匹配、最小点覆盖、最大独立集以及最大权闭合子图的联系
    没有点权和边权的时候,不讨论最大权闭合子图,最大匹配=最小点覆盖=点数-最大独立集最小点覆盖=点数-最大独立集:这个很好理解,考虑只有一条边的二分图的情况,点覆盖要求两个端点至少选一个,独立集要求两个端点最多选一个,是互补的关系,这意味着一个合法点覆盖的点集与一个合法独立集的......
  • 清晰易懂二分查找算法 你确定不看吗?
    @目录前言简介一、二分查找算法的原理是什么?1.确定搜索范围:2.计算中间位置:3.比较中间元素:4.调整搜索范围:5.重复迭代:二、二分查找算法的优缺点是什么?优点:缺点:三、java实现二分查找案例总结前言请各大网友尊重本人原创知识分享,谨记本人博客:南国以南i、提示:以下是本篇文......
  • 学习笔记 整体二分
    整体二分是一种离线算法记[l,r]为答案的值域,[L,R]为答案的定义域。(也就是说求答案时仅考虑下标在区间[L,R]内的操作和询问,这其中询问的答案在[l,r]内)我们首先把所有操作按时间顺序存入数组中,然后开始分治。在每一层分治中,利用数据结构(常见的是树状数组)统计当前查询的......
  • 冒泡 选择 二分
    importjava.util.Arrays;importjava.util.Random;importjava.util.Scanner;publicclassApp{publicstaticfinalintLENGTH=6;publicstaticRandomrandom=newRandom();publicstaticScannerscanner=newScanner(System.in);publi......
  • 整体二分
    学了一下,感觉不深刻。说是整体二分,不如说是离线的归并排序。考虑这个问题:LuoguP3834【模板】可持久化线段树2\(m\)次询问,每次询问给出\((l,r,k)\),问\([l,r]\)中第\(k\)小的值。我们首先先简化一下:如果\(m=1\),怎么维护?先二分出一个\(x\),建立树状数组维护\(\lex\)......
  • 二分法题目合集
    1.锯齿形数组找target有一个数组,前半部分有序,后半部分也有序,前半部分的开头元素大于后半部分的结尾元素,请从这个数组中找出target。解题思路:一开始我们就可以根据target和数组结尾元素的大小关系确定target属于哪个部分,之后将target和mid比较时就能根据位于哪一部分去更新l,r。......