公式

E - lt and le 解説 by MMNMM 印刷ページ


条件を緩め、すべての条件が \(t _ i=0\) であるときを考えます。

このとき、\(1,2,\ldots,N\) の \(N\) 頂点からなり、\(u _ i\) から \(v _ i\) への辺 \((1\le i\le Q)\) を張った有向グラフを \(G\) とすると、\(G\) において \(x\) から \(y\) に到達できるとき \(A _ x\le A _ y\) が成り立つ必要があります。 特に、\(G\) において同じ強連結成分にある頂点 \(x,y\) について \(A _ x\le A _ y\) および \(A _ x\ge A _ y\) より \(A _ x=A _ y\) が必要です。 逆に、\(G\) において異なる強連結成分にあるような任意の \(2\) つの頂点 \(x,y\) について \(A _ x\ne A _ y\) とすることができます(例えば、\(G\) の強連結成分に元のグラフの辺と対応する強連結成分の間に(自己ループを除いて)辺を張り、それのトポロジカル順序に沿って番号を付ければよいです)。

\(t _ i=1\) の条件があるときについて考えます。 同様のグラフを考えると、これの強連結成分内の \(2\) 頂点 \(x,y\) について \(A _ x=A _ y\) が必要であることは変わりません。 よって、同一の強連結成分内の \(2\) 頂点を結ぶ辺であって \(t _ i=1\) の条件に対応するものが存在するとき、条件を満たす列は存在しません。 逆に、そのような辺が存在しないとき、条件を満たす列は存在し、上と同様の構成が条件を満たします。

時間計算量は \(O(N+Q)\) となります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/scc>

int main() {
    using namespace std;
    unsigned N, Q;
    cin >> N >> Q;
    atcoder::scc_graph scc(N);
    vector<pair<unsigned, unsigned>> lt;
    for (unsigned i{}; i < Q; ++i) {
        unsigned t, u, v;
        cin >> t >> u >> v;
        --u;
        --v;
        scc.add_edge(u, v);
        if (t) lt.emplace_back(u, v); // t = 1 の辺をまとめておく
    }

    vector<unsigned> ans(N);
    // 強連結成分のトポロジカル順序に従って番号を付ける
    for (const auto& [i, component] : scc.scc() | views::enumerate)
        for (const auto x : component)
            ans[x] = i + 1;

    // 矛盾が生じたら 
    for (const auto& [u, v] : lt)
        if (ans[u] == ans[v]) {
            cout << "No" << endl;
            return 0;
        }
    cout << "Yes" << endl;
    for (string delim{}; const auto a : ans) cout << a << " ";
    cout << endl;
    return 0;
}

投稿日時:
最終更新: