準備
\(A\) が \(B\) より強いと分かっているとき,かつそのときに限り \(A\) から \(B\) に矢を張ったグラフ \(G\) を考える.
問題
Easy
辞書順を無視して,強い順に並べる. これは \(G\) においてトポロジカルソートするのと同じ.
Normal(本問)
辞書順最小の,強い順に並べる. トポロジカルソートで頂点を並べるとき, 選ぶ頂点の候補が複数あれば最小の物を選ぶようにすればよい. これは,入次数 0 の頂点を入れる入れ物として, min priority queue を用いれば良い.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vvll to(n);
vll in(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
to[a].emplace_back(b);
in[b]++;
}
min_priority_queue<ll> q;
rep(i,n){
if(in[i] == 0) q.push(i);
}
vll ans;
while(q.size()){
ll c = q.top(); q.pop();
ans.push_back(c+1);
for(auto d: to[c]){
in[d]--;
if(in[d] == 0) q.push(d);
}
}
assert(ans.size() == n);
coutv(ans);
return 0;
}