1042. 不邻接植花
2023-02-18 16:34:32 时间
1042. 不邻接植花
有 N 个花园,按从 1 到 N 标记。在每个花园中,你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外,没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
示例 1:
输入:N = 3, paths = [[1,2],[2,3],[3,1]]
输出:[1,2,3]
示例 2:
输入:N = 4, paths = [[1,2],[3,4]]
输出:[1,2,1,2]
示例 3:
输入:N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出:[1,2,3,4]
代码:
class Solution {
public:
vector<int> gardenNoAdj(int N, vector<vector<int> >& paths) {
vector<int> G[N];
for (int i=0; i<paths.size(); i++){//建立邻接表
G[paths[i][0]-1].push_back(paths[i][1]-1);
G[paths[i][1]-1].push_back(paths[i][0]-1);
}
vector<int> answer(N,0);//初始化全部未染色
for(int i=0; i<N; i++){
set<int> color{1,2,3,4};
for (int j=0; j<G[i].size(); j++){
color.erase(answer[G[i][j]]);//把已染过色的去除
}
answer[i]=*(color.begin());//染色
}
return answer;
}
};
相关文章
- 使用Commons Logging
- 记一次 .NET 某自动化采集软件 崩溃分析
- [C# 中的序列化与反序列化](.NET 源码学习)
- .NET 向量类型的运算结果范例——用于学习Vector类所提供百多个向量方法
- 树莓派(香橙派)通过.NET IoT 操作SPI编写屏幕驱动 顺手做个四足机器人(一)
- WPF自定义控件之消息提示
- .NET跨平台框架选择之一 - Avalonia UI
- 篇(16)-Asp.Net Core入门实战-权限管理之用户创建与关联角色(ViewModel再用与模型验证二)
- 学习ASP.NET Core Blazor编程系列十——路由(下)
- 代码生成器(CodeBuilder) 2.9.4 稳定版
- 篇(15)-入门实战-权限管理之用户创建与关联角色(ViewModel再用与模型验证一)
- 篇(14)-Asp.Net Core入门实战-权限管理之角色编辑和赋权(ViewModel-DTO初探)
- 算法-2 选择排序、冒泡排序、插入排序
- 篇(13)-Asp.Net Core入门实战-将功能代码增加异步功能Async和配置简单防范CSRF攻击
- NET 6 实现滑动验证码(一)、创建工程
- 算法-1 算法复杂度
- 在WPF中使用Prism弹出自定义窗体样式的对话框
- 使用Fody时,CS-SCRIPT动态代码无法找到程序集
- C# 使用SIMD向量类型加速浮点数组求和运算(3):循环展开
- aspnetcore两种上传图片(文件)的方式