[二分图] 学习笔记

Zwjay's Blog / 2023-08-15 / 原文

定义

无向图可以分成两个点集，集合内的点不相连通，不允许存在奇环

// 二分图的判定 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 2e6 + 10;
struct
{
	int to, next;
}e[M];
int top, h[N], color[N], n, m;

void add(int x, int y)
{
	e[++top] = {y, h[x]};
	h[x] = top;
}

bool dfs(int x, int c)
{
	color[x] = c;
	for (int i = h[x]; i ; i = e[i].next)
	{
		int y = e[i].to;
		if (!color[y])
		{
			if (dfs(y, (c == 1 ? 2 : 1))) return true;
		}
		else if (color[y] == c) return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	bool flag = false;
	for (int i = 1; i <= n; i ++)
	{
		if (!color[i])
			if (dfs(i, 1))
			{
				flag = true;
				break;
			}		
	}
	cout << (flag ? "No" : "Yes");
	
	return 0;
}

运用

题单

二分图染色

P1330 封锁阳光大学

可以把这题抽象为：给出一些初始为白色的点和一些连边，现要把一些点染成黑色，使白点和黑点都不会相邻，求最小染色数。

考虑不成立时，肯定出现奇环，跑二分图的判定即可。

考虑成立时，对于图中的每个子二分图，染色后分成两个黑白点集；

根据判定，手模一下易发现，每个子二分图的最小染色数就是取黑白点的更小值。

\(O(n+m)~\) down.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 2e5 + 10;
struct
{
	int to, next;
}e[M];
int top, h[N], color[N], n, m;

void add(int x, int y)
{
	e[++top] = {y, h[x]};
	h[x] = top;
}

bool dfs(int x, int c, int & wh, int  & bl)
{
	color[x] = c;
	if (c == 1) wh ++;
	else bl ++;
	for (int i = h[x]; i ; i = e[i].next)
	{
		int y = e[i].to;
		if (!color[y])
		{
			if (dfs(y, (c == 1 ? 2 : 1), wh, bl)) return true;
		}
		else if (color[y] == c) return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	bool flag = false;
	int ans = 0;
	for (int i = 1; i <= n; i ++)
	{
		if (!color[i])
		{
			int white = 0, black = 0;
			if (dfs(i, 1, white, black))
			{
				flag = true;
				break;
			}
			else
				ans += min(white, black);
//			printf ("i = %d white = %d black = %d\n", i, white, black);	
		}
	}
	if (flag) cout << "Impossible";
	else cout << ans;
	
	return 0;
}