CF547D Mike and Fish

这也能图论的一道题。

思路

对于 \(x\) 坐标相同的点，我们两两配对连边，多余的点不管。

对于 \(y\) 坐标相同的点，我们两两配对连边，多余的点不管。

这样就得到了若干个连通图，对这些连通图跑二分图染色即可得到答案。

证明：

由于是二分图染色，且横竖两两配对，由于连了边的点都不可能是相同的颜色，所以横竖都可以保证最少有 \(\lfloor \frac{n}{2} \rfloor\) 个点染成了一个颜色。

如果二分图染色不成功怎么办？

由于每个点最多两条边，所以说想要染色不成功只有可能是形成了奇数环。

这两条边一条横着一条竖着，我们不妨先加入环上所有的横边，设有 \(x\) 条。

这时形成了 \(x\) 个连通块，这些连通块想要形成环就必须添加 \(x\) 条竖边。

那么总边数就是 \(2x\) 条。

由于环上点数等于环边数，所以有 \(2x\) 个点，故得证不会有奇数环。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;

vector<int>E[maxn];

int col[maxn];

int lsth[maxn],lstw[maxn];

int n;

inline void dfs(int u,int tw)
{
    col[u]=tw;
    for(auto v:E[u]) if(col[v]==-1) dfs(v,tw^1);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;col[i]=-1;
        scanf("%d%d",&x,&y);
        if(lsth[x]){E[i].push_back(lsth[x]);E[lsth[x]].push_back(i);lsth[x]=0;}else lsth[x]=i;
        if(lstw[y]){E[i].push_back(lstw[y]);E[lstw[y]].push_back(i);lstw[y]=0;}else lstw[y]=i;
    }
    for(int i=1;i<=n;i++) if(col[i]==-1) dfs(i,0);
    for(int i=1;i<=n;i++) if(col[i]) putchar('r');else putchar('b');
}

题解 from:shadowice1984 题解 CF547D 【Mike and Fish】