AtCoder Beginner Contest 315E

ABC315E

トポロジカルソート． 本問題は DFS, BFS どちらでも可能である． どちらでも良いときは，DFS の方が実装が軽いケースが多い．
DFS のトポロジカルソートは，帰りがけ順で vertex を並べて， 最後に reverse.
試験本番では BFS で実装した． どこが間違っているのか分からなかった． 複数方法を持っていれば，一方が WA でももう一方で通せる可能性がある． 試験本番では，BFS に拘ってしまい，通せなかった．

BFS によるトポロジカルソートの場合， 単に reverse ではダメらしい． https://atcoder.jp/contests/abc315/editorial/6989

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vvll to(n);

  rep(i,n){

    ll c; cin >> c;

    vll p(c);

    rep(j,c) {

      cin >> p[j];  --p[j];

      to[i].push_back(p[j]);

    }

  }

 

  vll ans;

  vll vis(n);

  auto dfs = [&](auto dfs, ll cu, ll pa = -1) -> void {

    if(vis[cu]) return;

    vis[cu] = true;

    for(auto ne: to[cu]) {

      dfs(dfs, ne, cu);

    }

    if(pa!=-1) ans.push_back(cu+1);

  };

 

  dfs(dfs, 0);

  coutv(ans);

 

  return 0;

}