题目描述

难度分:$2600$

输入$n(1 \leq n \leq 2 \times 10^5)$和$n$个二维坐标点，范围$[1,2 \times 10^5]$。

你需要把每个点染成红色或者蓝色，使得每条水平线或垂直线上的红色点和蓝色点的数量之差至多为$1$。

输出染色方案，答案的第$i$个字符为r或b，表示输入的第$i$个点染成红色/蓝色。

输入样例$1$

4
1 1
1 2
2 1
2 2

输出样例$1$

brrb

输入样例$2$

3
1 1
1 2
2 1

输出样例$2$

brr

算法

二分图匹配

图论题，仍然是算法很模板，但是思路非常难想。

在读入所有点时，对$x$坐标相同的点两两配对，有剩下的点则不管。对所有$y$坐标相同的点两两配对，有剩下的点也不管。所有配对的点都连一条边建图，然后对图做染色法进行红蓝染色就可以得到我们的染色方案了。

复杂度分析

时间复杂度

建图的时间复杂度为$O(n)$，而染色法本质就是对图进行DFS，所有的点都要遍历到，时间复杂度还是$O(n)$。因此，算法整体的时间复杂度就是$O(n)$。

空间复杂度

染色数组$color$消耗的空间为$O(n)$；建图的瓶颈在于邻接表的空间消耗，为$O(n+m)$，其中$m$为边的数量，和$n$是同一级别。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;

int n, x, y;
int lstu[N], lstv[N], color[N];
vector<int> graph[N];

inline void dfs(int u, int c) {
    color[u] = c;
    for(int v: graph[u]) {
        if(color[v] == -1) {
            dfs(v, c^1);
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        color[i] = -1;
        graph[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        if(lstu[x]) {
            graph[lstu[x]].push_back(i);
            graph[i].push_back(lstu[x]);
            lstu[x] = 0;
        }else {
            lstu[x] = i;
        }
        if(lstv[y]) {
            graph[lstv[y]].push_back(i);
            graph[i].push_back(lstv[y]);
            lstv[y] = 0;
        }else {
            lstv[y] = i;
        }
    }
    for(int i = 1; i <= n; i++){
        if(color[i] == -1) {
            dfs(i, 0);
        }
    }
    for(int i = 1; i <= n; i++) {
        putchar(color[i]? 'r': 'b');
    }
    return 0;
}