红与蓝

链接：https://ac.nowcoder.com/acm/contest/9981/C

题目

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

输入与输出

输入

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

输出

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

思路

采用染色法,由于是一个树,那么无论从哪一个点开始染色都可以,不妨选择编号为 1 的点,先统计出以 1 号点为根节点的所有点的子树大小

再考虑每一个点 i :

1. 如果它与其父亲节点颜色相同,那么它的子树大小必须均为偶数(否则无法满足题意),且与 i 相连的点的颜色和 i 不同

2. 如果它与父亲节点颜色不同,那么它的字数大小必须有且只有一个是奇数，其他均为偶数,且为奇数的字数与 i 相连的点的颜色与 i 相同,其它与 i 相连的点
   的颜色与 i 不同

不难发现,如果有合法的染色方案,那么一定只有相反的两种方法,所以如果在染色的过程中无法满足题意,那么就一定不存在合法的染色方案了

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e6+7;

int n,head[maxn],cnt,color[maxn],sonNumber[maxn];//sonNumber表示子树大小
bool isFailed = false;//是否染色失败

struct Edge {
    int from, to;
}e[maxn<<1];

inline void add(int u, int v)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}

int calcSon(int nowPoint,int lastPoint)//计算子树大小,lastPoint表示上一个点
{
    int sum = 1;
    for(int i = head[nowPoint];i;i = e[i].from) {
        int nextPoint = e[i].to;
        if(nextPoint == lastPoint)
            continue;
        sum += calcSon(nextPoint, nowPoint);
    }
    return sonNumber[nowPoint] = sum;
}

void dfs(int nowPoint, int lastPoint, int nowColor)//用0,1表示点的颜色
{
    if(isFailed)
        return ;
    color[nowPoint] = nowColor;
    int cnt = 0 ;
    for(int i = head[nowPoint]; i; i = e[i].from) {
        int nextPoint = e[i].to;
        if(nextPoint != lastPoint)
            cnt += sonNumber[nextPoint] & 1;//判断它的子节点的树大小是否有且只有一个奇数
    }
    if(color[nowPoint] == color[lastPoint]) {//情况一
        if(cnt) {
            isFailed = true;
            return ;
        }
        for(int i = head[nowPoint]; i; i = e[i].from) {
            int nextPoint = e[i].to;
            if(nextPoint != lastPoint)
                dfs(nextPoint, nowPoint, nowColor^1);
        }
    }
    else {//情况二
        if(cnt != 1) {
            isFailed = true;
            return ;
        }
        for(int i = head[nowPoint]; i ;i = e[i].from) {
            int nextPoint = e[i].to;
            if(nextPoint != lastPoint) {
                if(sonNumber[nextPoint] & 1)//如果是大小为奇数的子树
                    dfs(nextPoint, nowPoint, nowColor);
                else
                    dfs(nextPoint, nowPoint,  nowColor^1);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x,y); add(y,x);
    }
    sonNumber[1] = calcSon(1, 0);
    dfs(1,0,1);
    if(isFailed)
        printf("-1\n");
    else {
        for(int i = 1; i <= n; ++i) {
            if (color[i])
                printf("B");
            else
                printf("R");
        }
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/05/10/2021-02-21-niuke01_C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！