考虑将每个点的横纵坐标看作点,将原先在坐标系上的点看作边,那么题目的要求即为将新图中的每条边定向后,每个点的入度出度的差的绝对值不大于 (1)。
因为度数为奇数的点的个数一定为偶数,所以可以将度数为奇数的点两两配对,在两点之间连一条边。这样每个点度数就都为偶数了,然后可以用欧拉回路来给每条边定向。每条边的方向就对应着原先在坐标系上的点的颜色。
和 Points and Segments 很像。
#include<bits/stdc++.h>
#define maxn 800010
#define d 200010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,tot,las;
int p[maxn],deg[maxn],bel[maxn];
bool vis[maxn],tag[maxn],used[maxn];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt=1;
void add(int from,int to)
{
e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
void dfs(int x)
{
tag[x]=true;
for(int &i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(vis[i]) continue;
used[i]=vis[i]=vis[i^1]=true,dfs(y);
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i)
{
int x,y;
read(x),read(y),y+=d;
add(x,y),bel[i]=edge_cnt^1,add(y,x);
deg[x]++,deg[y]++,p[++tot]=x,p[++tot]=y;
}
sort(p+1,p+tot+1),tot=unique(p+1,p+tot+1)-p-1;
for(int i=1;i<=tot;++i)
{
int x=p[i];
if(deg[x]&1)
{
if(las) add(las,x),add(x,las),las=0;
else las=x;
}
}
for(int i=1;i<=tot;++i)
if(!tag[p[i]])
dfs(p[i]);
for(int i=1;i<=n;++i) putchar(used[bel[i]]?'b':'r');
return 0;
}