[ABC223] D - Restricted Permutation

[Q] https://atcoder.jp/contests/abc223/submissions/26680736
検索：トポロジカルソート、辞書順

順序のある数列 = すぐにトポロジカルソートと分かったのに、はて、トポロジカルソートって何をして何が得られるんだっけと迷子になり大泣きしました。

1. 入次数をもとめながらグラフを張る。
2. 入次数が0 = 世間のしがらみから解放された頂点。いつ配置してもいい。
3. bfsで入次数0の頂点をスタート。1歩進めたら入次数を-1し、入次数が0になったらqueueにいれればよかった。

Q. 入力例1
4 3

2 1
3 4
2 4

1. indegとグラフはる。

G[1] = {}
G[2] = {1, 4}
G[3] = {4}
G[4] = {}

indeg[1] = 1
indeg[2] = 0
indeg[3] = 0
indeg[4] = 2

2. bfsをする。
priority_queue<ll, vector<ll>, greater<ll>> Q;
で、処理した順番がそのまま解答になる。

初期条件はindeg == 0 をみたす頂点なので、Q = {2, 3}

・2の処理
G[2] = {1, 4}なので、
--indeg[1] // 0
--indeg[4] // 1

めでたくindeg[1] == 0 になったので、Q.push(1)
・1の処理
G[1] = {}
もう末端なのでなにもない。

・3の処理
G[3] = {4}
--indeg[4] // 0

めでたくindeg[4] == 0　。世間のしがらみから解放されたので、Q.push(4)

・4の処理
G[4] = {}
末端なのでなにもしない。

A. 2 1 3 4

実装

int main(){
 cincout();
 
 ll N, M;
 cin >> N >> M;
 // 入次数が0になったらしがらみがない。
 vector<ll> G[N];
 ll indeg[N]{};
 rep(i, M){
   ll a, b;
   cin >> a >> b;
   --a, --b;
   G[a].push_back(b);
   ++indeg[b];
 }
 
 priority_queue<ll, vector<ll>, greater<ll>> Q;
 rep(i, N){
   if(indeg[i] == 0) Q.push(i);
 }
 queue<ll> ans;
 while (!Q.empty()){
   ll q = Q.top(); Q.pop();
   ans.push(q);
   for(auto v: G[q]){
     --indeg[v];
     if (indeg[v] == 0) Q.push(v);
   }
 }
 if ((ll)ans.size() < N) cout << -1 << endl;
 else{
   while (!ans.empty()){
     cout << ans.front()+1; ans.pop();
     if (!ans.empty()) cout << " ";
     else cout << endl;
   }
 }
}

https://atcoder.jp/contests/abc223/submissions/26680736