C. Online Courses In BSU ～3色dfs～

1500
  • Quiz
  • AC
  • 解説
    • パット見でトポロジカルソートっぽい。サイクルを見つけたら-1にすればいいと思うのだがそれは罠で、不要な講義でサイクルができていてもそれは-1ではない
    • トポロジカルソートっぽい時はdfsで解けることが多い
    • 講義の依存関係をどちらかの方向で有効辺にする発想は普通で、今回はaを取った後にしかbが取れない時、b->aの方向に辺を貼る
    • editorialの通り、不要なサイクルを無視するために、必須講義を始点としてdfsする
// editorial
void dfs(int u) {
    if (color[u] == 0) {
        color[u] = 1;
        for (int to: g[u])
            dfs(to);
        color[u] = 2;
        ord.push_back(u);
    } else if (color[u] == 1)
        cycle = true;
}
  • 解説つづき
    • このように未達部分をcolor=0, 今回のdfsで訪れた位置をcolor=1, 終わったらcolor=2とすると上手くいく
    • 「うまいな～」と思う。3色dfsと名付けよう
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    VI S(K); // specialty
    rep(i,K){
      cin>>S[i];
      S[i]--;
    }

    VV G(N);

    rep(i,N){
      ll n;cin>>n;
      while(n--){
        ll a;cin>>a;a--;
        // iを取るには事前にaを取る必要
        G[i].push_back(a);
      }
    }
    VI color(N);
    VI ord;
    
    bool cycle=false;
    function<void(ll)> dfs = [&](ll u){
      if(color[u]==0){
        color[u]=1;
        for(ll to : G[u]){
          dfs(to);
        }
        ord.push_back(u);
        color[u]=2;
      }else if(color[u]==1){
        cycle = true;
      }
    };

    for(ll s : S) dfs(s);

    if(cycle){
      p(-1);return 0;
    }

    p(SZ(ord));
    print_vector(ord,1);
    
    return 0;
}