【随缘一练】一棵树,请你给每个顶点染成红色或蓝色
每个 红色 顶点 蓝色
2023-09-14 09:13:08 时间
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持!
博主链接
问题描述
描述:
你拿到了一棵树,请你给每个顶点染成红色或蓝色。
要求:每个红点周围有且仅有一个红点,每个蓝点周围有且仅有一个蓝点。
“周围”的定义:某点周围的点指通过邻边直接连接的点。
所谓树,即没有自环、重边和回路的无向连通图。
输入描述:
第一行一个正整数 n,代表树的顶点个数.。(1≤n≤100000)
接下来的 n-1 行,每行两个正整数 u 和 v,代表点 u 和点 v 有一条边连接。 (1≤u,v≤n)
保证输入的一定是一棵合法的树。
输出描述:
如果可以达成染色的要求,请输出一个长度为 n 的字符串,第 i 个字符代表第 i 个顶点的染色情况,‘B’ 代表蓝色,‘R’ 代表红色。(若有多种合法染色的方法,输出任意一种即可)
否则直接输出-1。
示例1:
输入:
4
1 2
2 3
3 4
输出:
RRBB
说明:
1为红点,它连接的边有只有一个红点:2
2为红点,它连接的边有只有一个红点:1
3为蓝点,它连接的边有只有一个蓝点:4
4为蓝点,它连接的边有只有一个蓝点:3
示例2:
输入:
4
1 2
1 3
1 4
输出:
-1
说明:
可以证明,无论怎么染色,都无法满足题目的要求。
问题分析
- ①对于叶子节点,周围只有一个点就是它的父亲节点,题目要求每个点周围有且仅有一个红点/蓝点,所以叶子节点的颜色与其父亲节点的颜色一定是相同的;
- ②如果一个节点有多个叶子节点,那么整颗树是无法染色的,因为如果第一个叶子节点和父节点颜色都是R,根据题目要求第二个叶子节点应该是B,但是这样又不符合我们上面①分析的结果,所以如果一个节点有多个叶子节点,结果一定是 -1;
解题思路
-
我们使用深度优先搜索【DFS】遍历一次树,标记叶子节点及其父节点同色,将标记的点去掉后就会有新的叶子节点,然后重复这步操作。
- DFS遍历过程中,这个点若是叶子节点,将其与其父节点标记为同色,也就是赋予一个标记;
- 这个点不是叶子节点但未与子树中任何点同色,标记它和它的父亲节点同色;
- 如果同一个点被标记两次,则返回 -1;
- 如果根节点没有被标记,返回 -1;
-
再进行一次DFS,对节点上色。如果一个点与父亲节点标记相同,则颜色相同,如果标记不同,则颜色相反。
C代码
#include <stdio.h>
#include <string.h>
int mark = 0; //标记同色的父子节点
int head[100010]; // 存储树的索引节点
struct ty
{
int value; // 边的值
int next; // 相邻边的索引
}edge[200010];
int dp[100010]={0}; // 第一次DFS时,每个点的标记信息
int color[100010]={0}; // 第二次DFS时,记录每个节点的颜色信息
/* 添加新的边到树型结构中 */
void addedge(int x, int y,int pos)
{
edge[pos].value = y;
edge[pos].next = head[x];
head[x] = pos;
}
int dfs1(int x,int father)
{
int son=0;
for(int i=head[x];i != -1;i = edge[i].next)
{
if(edge[i].value != father) // 避免回环
{
++son;
if(dfs1(edge[i].value,x)) return 1;
}
}
// son==0表示叶子节点 ; dp[x]==0 表示 x 这个点未被标记
if(son == 0 || dp[x]==0)
{
if(dp[father] !=0) return 1; // 一个节点被多次标记,无解
dp[x] = dp[father] = ++mark;
}
return 0;
}
void dfs2(int x,int father)
{
for(int i=head[x];i != -1;i = edge[i].next)
{
if(edge[i].value != father) // 避免回环
{
if(dp[edge[i].value] == dp[x])
color[edge[i].value] = color[x]; // 两个节点标记相同,则颜色相同
else
color[edge[i].value] = !color[x]; // 两个节点标记不同,则颜色不同
dfs2(edge[i].value, x);
}
}
}
int main()
{
int x,y,n,pos=1;
scanf("%d",&n);
memset(head, -1, sizeof(head));
memset(edge, -1, sizeof(edge));
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
addedge(x, y,pos);
++pos;
addedge(y, x,pos);
++pos;
}
// 1==dfs1(1,0) 表示无解
// dp[0] 其实是整个树的第一个节点的根节点,上面的code中,我们的树是从pos==1开始的
// 也就是第一个节点的标记信息在dp[1]中,这里使用dp[0]就是为了观察第一个节点(dp[1])有没有被孤立
// 如果孤立了则dp[0]一定被标记了,反之dp[0]一定为0
if(dfs1(1,0) || dp[0])
{
printf("-1");
return 0;
}
color[1]=1; // 这里也可以是0,题目也说了可能多解
dfs2(1,0);
for(int i=1;i<=n;++i)
{
printf("%c",color[i]?'R':'B');
}
return 0;
}
这里是从善若水的博客,感谢您的阅读💯💯💯
相关文章
- Vue3.0实现todolist-实现todolist每个组件需要的数据
- python保存Excel中每个sheet内容为txt
- 2022-09-29:在第 1 天,有一个人发现了一个秘密。 给你一个整数 delay ,表示每个人会在发现秘密后的 delay 天之后, 每天 给一个新的人
- 研究证明:适度压力对认知有利,但不是每个人都受得住
- Pandas数据处理4、DataFrame记录重复值出现的次数(是总数不是每个值的数量)
- LeCun力荐!哈佛博士分享用GPT-4搞科研,细到每个工作流程
- SQL获取分组后取某字段最大一条记录(求每个类别中最大的值的列表)详解程序员
- Linux分支:各种选择让每个用户满意(linux的分支)
- 每个离不开便利店的人,都该去太原看看
- 每个Linux新手都应该记住的10个基本Linux命令
- 知识测试Linux知识,每个人都需要掌握!(测试需要掌握的linux)
- JavaScript计算字符串中每个字符出现次数的小例子