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;
}
投稿日時:
最終更新:
