CF1217D Coloring Edges

知识点： dfs 树。

题意

给定一张有向图，现在要求为图上所有的边进行染色，使得颜色种类最少的同时，同种颜色的边无法构成环，输出最少需要的颜色种类和任意一种染色可行方案。

思路

假设该有向图中不存在环，那么我们可以直接对所有的边染为同一种颜色。因此可以先做一遍拓扑判断有没有环。

有环后情况就变了：我们需要最少多少种颜色才可以将图进行染色呢？

答案是 \(2\) 种。假设图中构成环，那么我们对环可以直接交替染两种颜色，这样就可以满足条件。

现在问题是有没有一种好一点的写法，让我们可以更加方便的染色呢？

我们假设该有向图是连通的，同时只有一个入度为 \(0\) 的节点，且从这个点出发可以到达所有的点。如果对这个定义思考其相关的东西的话，那么很自然的，一种是拓扑排序，另一种，就是树。

如果我们从这个特殊的节点开始遍历，每个节点只遍历一次，那么很明显我们所经过的边和点构成了一棵树，一颗 dfs 树。如果我们仔细想想染色的话，那么自然的，我们挑出来构成树的边，都可以染为同一种颜色。那么这就是其中一种颜色了。

那么不在我们的搜索树中的边又如何呢？可以发现，如果边不在我们的搜索树中，那么这条边，要么是指向了其树上祖先，要么是指向其子树中的其中一个节点，要么，就是与其某个祖先的所有子树中，不与这个节点所在的子树一起的子树中。那么我们就需要接着考虑这三种边各自的染色方案了。

对于指向其祖先的边，很自然的，这条边会使得树构成一个环，此时该边只能染另外一种与树边不同的颜色了；
对于指向其子树中某个节点的边，类似于拓扑排序，这条边不会构成环，可以放心染为树边的颜色；
对于指向另外子树的边，也可以类似于拓扑排序的步骤，这条边依然不会构成环，也可以放心染为树边的颜色。

因此，我们已经有了比较简单的染色方案了，最后剩下一个小问题：这三种边怎么确定？

可以发现的是，对于其中两种边，其染色方案是一样的，只有返回祖先的边会构成环，那么我们必须要确定，哪些边是返祖边，另外两种边归于一类。

我们注意一下我们是怎么构建出这棵树的？通过 dfs 的形式。

对于返祖边来说，以返回到的节点为根的子树还没有完全遍历完；
对于其他两条边的，访问到的节点其所有子树已经遍历结束；
对于树边，那么接下来访问的节点还未访问。

因此，我们可以设点的三种状态，0 1 2 分别代表未访问、该点的子树未遍历结束、该点的子树已经遍历完毕，最后我们根据上述列出来的性质和对三种边和树边的染色方案进行染色，即可。

实现

void std::ranges::macro::Main() {
    int n, m;
    cin >> n >> m;

    vector adj(n, vector<pair<int,int>>{});
    vector<int> ind(n);
    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        u --; v --;
        adj[u].emplace_back(v, i);
        ind[v] ++;
    }

    vector<int> seq;
    for (int i = 0; i < n; i ++) if (ind[i] == 0) seq.emplace_back(i);
    for (int i = 0; i < n && i < seq.size(); i ++) {
        int from = seq[i];
        for (auto [to, _] : adj[from]) {
            if (-- ind[to] == 0) {
                seq.emplace_back(to);
            }
        }
    }
    if (seq.size() == n) {
        cout << 1 << '\n';
        for (int i = 0; i < m; i ++) cout << 1 << " \n"[i == m - 1];
        return;
    }

    vector<u8> state(n);
    vector<int> col(m, -1);
    auto dfs = [&](auto &self, int from) -> void {
        state[from] = 1;
        for (auto [to, eid] : adj[from]) {
            if (state[to] == 0) {
                self(self, to);
                col[eid] = 1;
            } else if (state[to] == 1) {
                col[eid] = 2;
            } else {
                col[eid] = 1;
            }
        }
        state[from] = 2;
    };
    for (int i = 0; i < n; i ++) {
        if (state[i] == 0) {
            dfs(dfs, i);
        }
    }

    assert(find(col, -1) == col.end());
    cout << max(col) << '\n';
    for (auto item : col) cout << item << ' ';
    cout << '\n';
}