Discussion #2110 - Problem #4243

神仙题 orz。

无向图并不好做。考虑先给图定向。根据颜色从小到大连边。因为保证相邻点颜色不同，因此连出来一定是一个 DAG。

考虑求出到每个点的最长路。不失一般性地，我们假设整个 DAG 构成一个连通分量。

给出结论：每个节点染成的颜色即为以该节点结尾的最长路长度，记为 $f_v$。证明很简单。假设 $u \rightarrow v$ 有一条边，那么 $f_v \geq f_u+1$。因此这个方案一定合法。

拓扑排序即可。非常好写。

QOJ.ac