21年基础训练营1C红与蓝（图论视角）

近来由于进行蓝桥杯训练，开始复盘总结自己以前做过的搜索题目。
由于前几天复习了图论，发现这个题目有一些图论的味道，so 因此记录一下心得。
link

题目大体描述

给定一个无根树，请你对使用两种颜色对之染色。使得蓝色周围有且只有一个蓝色，红色周围有且只有一个红色，若能染色成功则输出染色序列。

思路

对本题目而言，我请读者思考这个题目如果翻译为图论语言该如何理解？
显然，我们可以这样理解：
一个节点与之相连的同色点有且仅有一个。mean what?
首先想到二分图的匹配，但是一看这东西不算是一个二分图。
我们结合著名定义：图者，二元关系之集合也，图论，位置之几何也。

那么显然我们想当然的会认为树的节点就是我们要建立的图的顶点。一个同样自然的想法就是顶点的性质就是点的颜色。
那么我们该如何定义他们的边的性质呢？
首先边同样是树相连的边而继承而来的。边的性质应当从节点的性质中总结出来。
那么可以就是边表示相连接的顶点它们is同色or异色
(当然同色和异色这些东西我也是看了雨巨的解答后发现的，但是我认为这样从零开始推理还是比较自然的一种理解，本段落主要是我在练习我的图论抽象能力，若有其他的理解请评论区交流。)
这样就好办了，我们可以不管是观察也好，分析样例也好我们能够推理出这样一个结论————叶子节点的颜色与他的父亲一定相同。叶子节点的父亲和叶子节点父亲的父亲颜色一定相反。
于是如何遍历对于这个题目来说一个图论意义上的解答就出现了。
遍历这个树生成一个同色的并查集和一个异色边构成的图。遍历图的每一个边判断是否与并查集冲突。（//检测是否有解。）
再次遍历图将与一个区块相连的所有区块都在并查集中连接起来。（//目的是输出一个成功可行的染色序列。）

code