IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 树形DP:配对染色 -> 正文阅读

[数据结构与算法]树形DP:配对染色

问题引入

描述
给定一棵树,为每个顶点染成红色或蓝色。

要求:每个红点周围有且仅有一个红点,每个蓝点周围有且仅有一个蓝点。
“周围”的定义:某点周围的点指通过邻边直接连接的点。
所谓树,即没有自环、重边和回路的无向连通图。

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

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

求解思路

典型的树的遍历问题,树形DP的思想是,在一次树的遍历过程中,完成对应问题的求解,(填充对应的DP数组),由于树的问题的求解总是依赖于子结构的求解,往往的求解思路是:

通过DFS等遍历方式,在后序遍历的过程中完成对应问题的求解。

本题的要求是,对于当前节点,其颜色与有且仅有一个相邻节点相同。那么可以有以下的推论:

  1. 叶子节点只有一个相邻节点,因此叶子节点与其父亲节点颜色相同
  2. 父亲节点已经与叶子节点颜色相同,因此父亲节点的父亲节点颜色必然不同

实现过程

采取后序遍历的实现方式,dp[i]=0 初始化为i节点未染色,后序遍历过程,如果cur节点与其一个子节点next都是 dp[idx]=0 都是未染色,那么当前两个节点可以染成相同的颜色,(采取将dp[]=cur)标记位cur表示两者相同的颜色)

在这里插入图片描述

以一颗最简单的三个节点的树为例,一开始由于初始化dp[]={0}

  • 因此首先遍历过程中,遇到的两个父子并且未染色的是节点1、节点2 两者可以染色为同色,dp[1]=dp[2]=1

  • 当遍历到节点1和节点3时,由于节点1已经染色(被抢占)因此节点3无法寻找到配对,说明整个方案不可行

当完成dp[]数组的填充后,下一步是进行实际的填色过程,由于只有两种颜色,因此只需要遍历过程中记录当前的dp[]与parent是否相同即可:

  • 若相同,那么color[cur]=color[pre]
  • 若不同,那么color[cur]=!color[pre]

代码实现

#include<iostream>
#include<vector>
using namespace std;
vector<int> mp[100001]; //mp[u]表示从u节点的 相连节点集合
int color[100001];//颜色矩阵
int dp[100001]={0}; //dp[i]!=0  表示这个位置需要上一个色 (一般是 [parent,son] 一组)
void dfs1(int pre,int index)
{
     
    //研究从index开始 其所在子树的上色问题
    for(int i=0;i<mp[index].size();i++)
    {
        int next=mp[index][i];//孩子节点
        if(next==pre)
            continue; //跳过环路
        dfs1(index,next); //已完成子问题求解 因为填色问题可以从叶子节点开始确定

        if(!dp[index] && !dp[next])   //
        {
            
            dp[index]=index;
            dp[next]=index;  //全部调整为index数值
        }
    }

}
//开始调整颜色
void dfs2(int pre,int index)
{
    for(int i=0;i<mp[index].size();i++)
    {
        int next=mp[index][i];
        if(next==pre)
        {
            continue;
        }
        if(dp[next]==dp[index])  //下一个节点和当前节点同一颜色
            color[next]=color[index];
        else
            color[next]=!color[index];
        dfs2(index,next);//进入下一入口

    }
}



int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    //
    
    dfs1(-1, 1);
    
    for(int i=1;i<=n;i++)
    {
       
        if(dp[i]<=0)  //存在无法染色的节点
        {
            cout<<-1<<endl;
            return 0;
        }
        
    }
        
    color[1]=1;
    dfs2(-1,1);
    for(int i=1;i<=n;i++)
    {
        if(color[i]==1)
            cout<<"R";
        else
            cout<<"B";
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-10 11:18:39  更:2021-12-10 11:20:21 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 14:23:05-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码