题目链接：Codeforces 1217 D

你有一个包含 $n$ 个点和 $m$ 条边的有向图（没有自环或重边）。

定义一张图的 $k$ 染色为：将每条边染成 $k$ 种颜色中的一种。一个 $k$ 染色是好的当且仅当不存在一个环满足环上的所有边颜色相同。

你需要求出这张图的 $k$ 染色，并最小化 $k$ 的值。

数据范围：$2 \le n \le 5000$，$1 \le m \le 5000$。

Solution

结论：最优的 $k$ 一定满足 $1 \le k \le 2$。其中 $k = 1$ 当且仅当这张有向图没有环。

没有环的情况下 $k = 1$ 显然成立，我们只需要证明有环的情况下 $k$ 可以取到下界 $2$。

考虑建出原图的 $\text{DFS}$ 树，那么对于一条树边 $u \rightarrow v$ 一定有 $u$ 的 $\text{DFS}$ 序小于 $v$ 的 $\text{DFS}$ 序；对于一条返祖边 $u \rightarrow v$ 则刚好相反。

那么对于一个环，这两类边一定都存在；我们只需要把树边染成 $0$，返祖边染成 $1$ 就能满足条件了。具体实现过程中和 $\text{Tarjan}$ 缩点类似。

时间复杂度：$\mathcal O(n + m)$。

Code

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 5e3;

int n, m, ans[N + 5], sta[N + 5];
std::vector<std::pair<int, int>> e[N + 5];

void addEdge(int u, int v, int x) {
    e[u].push_back(std::make_pair(v, x));
}
void dfs(int u) {
    sta[u] = 1;
    for (auto v : e[u]) {
        if (sta[v.first] == 0) {
            ans[v.second] = 1, dfs(v.first);
        } else if (sta[v.first] == 1) {
            ans[v.second] = 2;
        } else {
            ans[v.second] = 1;
        }
    }
    sta[u] = 2;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int u, v, i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v, i);
    }
    for (int i = 1; i <= n; i++) if (sta[i] == 0) dfs(i);
    printf("%d\n", *std::max_element(ans + 1, ans + m + 1));
    for (int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]);
    return 0;
}