Educational Codeforces Round 72 D. Coloring Edges

問題: https://codeforces.com/contest/1217/problem/D

公式解説: https://codeforces.com/blog/entry/69605

問題概要

$ n (\leq 5000) $ 頂点 $ m (\leq 5000) $ 辺の有向グラフがある．このグラフの辺を，「含まれる辺が全て同じ色で塗られた閉路」がないように彩色したい．色の数を最小化した上で条件を満たす彩色を1つ答えよ．

解法概要

グラフが閉路を含まない場合，自明に1彩色可能． グラフが閉路を含むかどうかの判定方法はいろいろあるが，私の解法ではトポロジカルソートで全頂点を並べることができれば閉路なし，できなければ閉路ありとしている．

グラフが閉路を含む場合，1彩色は不可能である． ここで，頂点番号に着目してみる． 頂点番号 $ u $ から頂点番号 $ v $ への辺があるとすると， 1つの閉路には $ u \gt v $ となるような辺と $ u \lt v $ となるような辺が必ず両方含まれる． これは例えば，$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l \rightarrow u_1 $ というような1つの閉路があるとき，以下の3つの場合に場合分けするとわかりやすい．

• $ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \gt u_{i+1} $ となるような辺と $ u_i \lt u_{i+1} $ となるような辺が両方含まれていれば，閉路の中にも両方自明に含まれる．

• $ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \gt u_{i+1} $ となるような辺のみなら，$ u_l \lt u_1 $ なので，閉路の中には両方含まれる．

• $ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \lt u_{i+1} $ となるような辺のみなら，$ u_l \gt u_1 $ なので，閉路の中には両方含まれる．

したがって，$ u \gt v $ となるような辺を色1， $ u \lt v $ となるような辺を色2で彩色すれば問題の条件を満たす2彩色が可能である．また，色を3色以上使う必要はない．

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

constexpr int MAX_N = 5000;

struct Edge {
    int u, v, color;
    Edge(int u, int v, int color): u(u), v(v), color(color) {}
};

int n, m, k = 1;
vector<int> G[MAX_N];
vector<Edge> edges;

vector<int> topological_sort(){
    int indeg[n];
    set<int> st; // 入次数が0の頂点の番号
    fill(indeg, indeg+n, 0);
    for(int i=0;i<n;++i) for(int to: G[i]) indeg[to]++;
    for(int i=0;i<n;++i) if(indeg[i] == 0) st.insert(i);

    vector<int> ret;
    int used[n];
    fill(used, used+n, 0);
    while(!st.empty()){
        int node = *st.begin();
        st.erase(node);
        ret.push_back(node);
        used[node] = 1;
        for(int next: G[node]){
            --indeg[next];
            if(!used[next] && indeg[next] == 0) st.insert(next);
        }
    }
    return ret;
}

int main() {
    cin >> n >> m;
    int u, v;
    for(int i=0;i<m;++i) {
        cin >> u >> v;
        --u; --v;
        edges.push_back(Edge(u, v, 1));
        G[u].push_back(v);
    }

    vector<int> ordered_nodes = topological_sort();
    vector<int> c(m, 1);
    if(ordered_nodes.size() == n) {
        k = 1;
    } else {
        k = 2;
        for(int i=0;i<m;++i) {
            if(edges[i].u > edges[i].v) c[i] = 2;
        }
    }

    cout << k << endl;
    for(int i=0;i<m-1;++i) cout << c[i] << " ";
    cout << c[m-1] << endl;
}

所感

ブログを更新しない間に AtCoder のレートが破滅していました．心当たりはいろいろありますが，そのうち1つが「解説ブログの更新をサボっていた」なので今週からまた1週間1記事以上を目標に頑張ります．