【二分图染色】Codeforces 547D Mike and Fish

题面在这里

题意：给平面上n个点黑白染色，使得每一行或每一列两种颜色数量差不超过1

​

考虑这样建图：

对每一行的相邻两个点连边，每一列相邻两个点连边

因为连的边都是平行于坐标轴的，所以不存在奇环，就一定是二分图了

然后二分图黑白染色就是一个可行答案

​

示例程序：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn=200005,maxe=800005;
int n;
int son[maxe],nxt[maxe],lnk[maxn],tot;
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
struct data{
	int x,y;
}a[maxn];
vector<int> X[maxn],Y[maxn];
bool vis[maxn],s[maxn];
void dfs(int x){
	vis[x]=1;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!vis[son[j]])
	  s[son[j]]=s[x]^1,dfs(son[j]);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),X[a[i].x].push_back(i),Y[a[i].y].push_back(i);
	for (int i=1;i<=2e5;i++){
		for (int j=0;j<X[i].size();j++)
		 if ((j^1)<X[i].size()) add(X[i][j^1],X[i][j]);
		for (int j=0;j<Y[i].size();j++)
		 if ((j^1)<Y[i].size()) add(Y[i][j^1],Y[i][j]);
	}
	for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
	for (int i=1;i<=n;i++) putchar(s[i]?'r':'b');
	return 0;
}