この問題では、トポロジカルソートというアルゴリズムが求められます。グラフの言葉に言い換えると、以下のようになります。

$N$ 頂点 $M$ 辺有向グラフであり、$i$ 本目の辺は頂点 $B_i$ から $A_i$ の有向辺です。トポロジカルソートをした結果の列としてあり得るもののうち、辞書順最小のものを出力してください。

この問題は、以下のように解くことが出来ます。

• 始め、それぞれの頂点の出次数を持った配列と集合を管理するデータ構造 \(S\) を持ちます。入次数が \(0\) である頂点を全て \(S\) に入れます。

• 以下を \(N\) 回繰り返します。

  • \(S\) に含まれる要素のうち最小のものを取り出し、これを \(v\) とする。トポロジカルソートの結果の末尾に \(v\) を加え、\(v\) に辺が出ている頂点達の入次数を \(1\) ずつ減らし、\(0\) になったものがあれば \(S\) に追加する。

この結果得られた列が解となります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  set<int> s;
  vector<int> d(n);
  vector<vector<int>> g(n);
  vector<int> ans;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    d[b]++;
    g[a].push_back(b);
  }
  for(int i=0;i<n;i++) if(d[i]==0) s.insert(i);
  while(s.size()){
    int v=(*s.begin());
    cout<<v+1<<" ";
    s.erase(v);
    for(auto e:g[v]){
      d[e]--;
      if(d[e]==0) s.insert(e);
    }
  }
  cout<<endl;
}