网站设计首页框架图片百度手机助手官网

将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图

二分图：一定不含有奇数个点数的环；可能包含长度为偶数的环， 不一定是连通图

染色可以使用1和2区分不同颜色，用0表示未染色
遍历所有点，每次将未染色的点进行dfs, 默认染成1或者2
由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败就能立刻break/return

染色失败相当于存在相邻的2个点染了相同的颜色，即点的个数的奇数个

染色法判定二分图：

#include <iostream>
#include <cstring>using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // 由于是无向图, 顶点数最大是N，那么边数M最大是顶点数的2倍
int e[M], ne[M], h[N], idx;//邻接表
int st[N];//该点的颜色void add(int a, int b)
{
//头插法//如图 如1与2之间要有一条线，让2的ne为1，再让h[1]为2的索引。//这样h[1]就是1节点存的最后一个相连的点，如图就是7节点。//而在索引表内部，通过头插法的方式(即每次ne指向上一个点(h存的就是上一个点))，索引表为：7->4->2e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool dfs(int u, int color) 
{st[u] = color;for(int i = h[u]; i != -1; i = ne[i]){//遍历邻接表int j = e[i];if(!st[j]) //若还没颜色，则递归下去染色{//递归下去if(!dfs(j, 3 - color)) return false;//如果当前是3-2=1，则下一次是3-1=2，以此类推，奇数和偶数的点颜色不一样}//如果该点有颜色，则判断该点的颜色是否跟邻接表的头点颜色相同，相同则说明矛盾else if(st[j] == color) return false;}return true;
}int main()
{int n, m;scanf("%d%d", &n, &m);memset(h, -1, sizeof h);while (m --){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b,a);  // 无向图，a->b, b->a}bool flag = true;for(int i = 1; i <= n; i ++){if(!st[i]){if(!dfs(i, 1))//如果返回FALSE，则说明有矛盾发生，flag赋为FALSE{flag = false;break;}}}if(flag) printf("Yes\n");else printf("No\n");return 0;
}