旺崽的博客

要么天赋异禀，要么天道酬勤

0%

2021牛客寒假算法基础集训营1 C.红和蓝

发表于 分类于 Valine：

题目链接

题目描述

你拿到了一棵树，请你给每个顶点染成红色或蓝色。
要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
“周围”的定义：某点周围的点指通过邻边直接连接的点。
所谓树，即没有自环、重边和回路的无向连通图。

输入描述:

第一行一个正整数 $n$，代表树的顶点个数。$(1 \leq n \leq 100000)$
接下来的 $n-1$ 行，每行两个正整数 $u$ 和 $v$，代表点 $u$ 和点 $v$ 有一条边连接。 $(1 \leq u,v \leq n)$
保证输入的一定是一棵合法的树。

输出描述:

如果可以达成染色的要求，请输出一个长度为 $n$ 的字符串，第 $i$ 个字符代表第 $i$ 个顶点的染色情况，’B’ 代表蓝色，’R’ 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出 $-1$。

示例1

输入

1
2
3
4
4
1 2
2 3
3 4

输出

1
RRBB

示例2

输入

1
2
3
4
4
1 2
1 3
1 4

输出

1
-1

题解写得有点复杂，我换种思路，采取自底向上染色的方法，对一个叶子结点来说，显然它只能和其父亲同色，我们就给其一对相同的编号，若遍历一遍树刚好能拆成偶数对，证明可以染色，那再遍历一遍染色即可，编号过程如下图：
在这里插入图片描述
若在编号过程中发现某一结点的父亲已经染色，证明其父亲已和其他结点组成一对，那么这个结点必无法染色，则直接输出 $-1$ 即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
int n, x, y, cnt, id[N] = {1}, ans[N];

void dfs1(int son, int father) {//编号
    for (auto kid:G[son]) {
        if (kid != father) dfs1(kid, son);
    }
    if (!id[son]) {
        if (id[father]) {//若父亲结点已被编号直接输出-1
            printf("-1\n");
            exit(0);
        }
        id[father] = id[son] = ++cnt;
    }
}

void dfs2(int son, int father, int color) {//染色
    ans[son] = color;
    for (auto kid:G[son]) {
        if (kid != father) dfs2(kid, son, (id[kid] == id[son] ? color : color ^ 1));
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    for (int i = 1; i <= n; i++) putchar(ans[i] ? 'R' : 'B');
    return 0;
}