Submission #35069435

---

Source Code Expand

// O(N^2) 辺 + 密グラフ Dinic
#include <bits/stdc++.h>
#include <atcoder/dsu>
#include <atcoder/scc>

namespace atcoder {

namespace internal {

template <class T> struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class Cap> struct mf_graph {
  public:
    mf_graph() : _n(0) {}
    explicit mf_graph(int n) : _n(n), g(n, std::vector<bool>(n)) {}

    void add_edge(int from, int to) {
        g[from][to] = true;
    }

    Cap flow(int s, int t) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> level(_n), iter(_n);
        internal::simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (int i = 0; i < _n; i++) {
                    if (!g[v][i] || level[i] >= 0) continue;
                    level[i] = level[v] + 1;
                    if (i == t) return;
                    que.push(i);
                }
            }
        };

        auto dfs = [&](auto dfs, int v) -> bool {
            if (v == s) return true;
            int level_v = level[v];
            for (int& i = iter[v]; i < _n; i++) {
                if (!g[i][v] || level_v <= level[i]) continue;
                const bool d = dfs(dfs, i);
                if (!d) continue;
                g[v][i] = true;
                g[i][v] = false;
                return true;
            }
            level[v] = _n;
            return false;
        };

        auto dfs_first = [&](int v) -> Cap {
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < _n; i++) {
                if (!g[i][v] || level_v <= level[i]) continue;
                const bool d = dfs(dfs, i);
                if (!d) continue;
                g[v][i] = true;
                g[i][v] = false;
                res++;
            }
            level[v] = _n;
            return res;
        };

        Cap flow = 0;
        while (true) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            Cap f = dfs_first(t);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    int _n;
    std::vector<std::vector<bool>> g;
};

}  // namespace atcoder

using namespace std;
using u64 = uint64_t;


vector<int> solve(int N, vector<pair<int, int>> edge){
    sort(edge.begin(), edge.end());
    const int S = N * 2, T = S + 1;
    atcoder::mf_graph<int> g(T + 1);
    for(int i = 0; i < N; i++){
        g.add_edge(S, i);
        g.add_edge(N + i, T);
    }
    for(int ii = 0; ii < N; ii += 64){
        vector<u64> bit(N);
        for(int i = 0; i < min(N - ii, 64); i++){
            bit[ii + i] |= u64{1} << i;
        }
        for(auto& [A, B] : edge) bit[B] |= bit[A];
        for(int i = 0; i < min(N - ii, 64); i++){
            bit[ii + i] ^= u64{1} << i;
        }
        for(int j = ii; j < N; j++) for(int i = 0; i < 64; i++) if(bit[j] & u64{1} << i){
            g.add_edge(ii + i, N + j);
        }
    }
    g.flow(S, T);
    atcoder::dsu uf(N);
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
        if(g.g[N + j][i]) uf.merge(i, j);
    }
    unordered_map<int, int> color;
    vector<int> answer(N);
    for(int i = 0; i < N; i++) answer[i] = color.try_emplace(uf.leader(i), color.size()).first->second;
    return answer;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> edge(M);
    atcoder::scc_graph g(N);
    for(auto& [A, B] : edge){
        cin >> A >> B;
        A--; B--;
        g.add_edge(A, B);
    }
    auto scc = g.scc();
    const int n = scc.size();
    vector<int> idx(N);
    for(int i = 0; i < n; i++) for(int j : scc[i]) idx[j] = i;
    for(auto& [A, B] : edge){
        A = idx[A];
        B = idx[B];
        assert(A <= B);
    }
    edge.erase(remove_if(edge.begin(), edge.end(), [](pair<int, int> a){ return a.first == a.second; }), edge.end());
    auto color = solve(n, move(edge));
    vector<int> answer(N);
    for(int i = 0; i < N; i++) cout << color[idx[i]] + 1 << " \n"[i + 1 == N];
}

Submission Info

Judge Result