UVa 10004 - WinDaLex/Programming GitHub Wiki

Bicoloring

from Volume 2. Data Structures :: Graphs

Description

输入一张图，给所有节点染色，直接相连的节点必须是不同颜色的。输出是否可以只用两种颜色染完这张图。

Solution

DFS 去模拟染色过程，每次都用与自己不同的颜色去染，发现已经染色的节点则检查颜色是否正确。一旦出现矛盾，就说明无法实现 bicoloring 。