Codeforces 1217D – Coloring Edges

题目链接:Codeforces 1217D

题目要求给出一种边的染色方案,使得所有的环上必须存在至少两种颜色,并且用的颜色数量最少。

在有向图上DFS的时候,每出现一个返祖边,就出现一个环,只要让返祖边的颜色与其他的边不一样即可,所以最多有两种颜色。我们可以在用栈维护当前DFS的链,然后寻找返祖边即可。

渐进时间复杂度$O(n + m)$。

 

说点什么

avatar
50
  Subscribe  
提醒