Codeforces 663C Graph Coloring (图染色)

给出一张图,每条边都有一个颜色(要么是红色要么是蓝色),如果翻转一个顶点,那么这个顶点相邻的边都会变色(红变蓝,蓝变红),求使得整个图变成同色的最小操作数,并且输出要翻转哪些顶点。

最小操作数一定是全部变成红色和全部变成蓝色操作数的最小值,我以全部变成红色举例:如果一条边是红色,那么这条边的两个顶点必然是:要么同时不翻转要么同时翻转,如果一条边是蓝色,那么这条边的两个顶点翻转的情况肯定是不一致的,我们不妨将翻转情况一致的放在同一个集合, 那么就会有两个集合,一个表示翻转的点一个表示不翻转的点。那么这个问题就变成图的染色问题,dfs或者bfs染色即可,因为集合可以通过翻转互补,一个连通块的最小操作数就是最小那个集合的尺寸。

 

LEAVE A COMMENT