【Codeforces 547D】Mike and Fish | Mrsrz's blog

欧拉回路

题目大意：

给定二维平面上的 $n$ 个点，要求染色成红色或蓝色，使得每行每列中，两种颜色的点的个数差不超过 $1$。

求方案。

题解：

还是把横、纵坐标看成点，点当成边。要求给边定向，使得每个点的出度和入度的差不超过 $1$。

相当于欧拉路径（回路则为 $0$）。

可以新增一个 $0$，向所有度数为奇数的点（一定是偶数个）连边。则只需要找欧拉回路即可。

找欧拉回路，从任意一个点开始一直走，把边扔栈里。按照回溯时的顺序排列即为一条回路。

边走边定向即可。

时间复杂度 $O(n)$。

Code：

#include<iostream>
using namespace std;
const int N=8e5+5;
int n,vis[N],deg[N],nod,col[N],cnt,head[N];
struct edge{
    int to,nxt,id,_id;
}e[N<<1];
void dfs(int now){
    for(int&i=head[now];i;i=e[i].nxt)
        if(!vis[e[i].id]){
            --deg[now],--deg[e[i].to];
            vis[e[i].id]=1;
            if(now<=200000)col[e[i]._id]=1;
            dfs(e[i].to);
        }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        int u,v;
        cin>>u>>v;
        v+=200000;
        ++nod;
        e[++cnt]=(edge){u,head[v],nod,i},head[v]=cnt;
        e[++cnt]=(edge){v,head[u],nod,i},head[u]=cnt;
        ++deg[u],++deg[v];
    }
    for(int i=1;i<=400000;++i)
        if(deg[i]&1){
            ++nod;
            e[++cnt]=(edge){0,head[i],nod,0},head[i]=cnt;
            e[++cnt]=(edge){i,head[0],nod,0},head[0]=cnt;
            ++deg[0],++deg[i];
        }
    for(int i=1;i<=400000;++i)
        if(deg[i]){
            dfs(i);
        }
    for(int i=1;i<=n;++i)
        if(col[i])cout.put('r');else cout.put('b');
    return 0;
}