乐趣区

关于leetcode1042的思考

题目:
有 N 个花园,按从 1 到 N 标记。在每个花园中,你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外,没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

题目属于图的渲染~ 由于诸多限定条件仅仅须穷举出其中一个解即可~
思路~
1 将 paths 的所有元素存储在一副图 graph 中~
2 对各个节点进行边的遍历并染色(这是重点)但是呢?怎么个染色法呢?
不妨可以这样思考~4 种颜色设为 bool 类型 对 N 个节点一次进行染色~
首先第一个节点 先查询其邻点是否已染比如颜色 k (这里颜色不妨用 1,2,3,4 替代) 当染了颜色 k 遍在结果
集里面 res[0]=k; 之后若有其他节点的邻点是第一个节点 则可以直接取到 res[0]也就是 k 这里将能取到的邻点都设置为 true 也就是已经染色 即可 然后 穷举遍历 一次性即可完成操作

for(int i=0;i<N;i++){vector<bool> used(5,0);
for(auto j: gragh[i])
    used[res[j]]=true;
}
for(int k=1;k<5;++k)
{if(!used[k])res[i]=k;return;
}
退出移动版