054 - Takahashi Number（★6）別解 setで済んだら消していく

• Quiz
  • https://atcoder.jp/contests/typical90/tasks/typical90_bb
• AC (7/12 20:00以降に見れます)
  • https://atcoder.jp/contests/typical90/submissions/23306592
• 解法
  • ランクを0, 1, 2, ...の順に確定していく
  • 確定中に参照した本はその時点で関係者全てのランクが決まるので、もう参照する必要はなくなり、setから消してよい
  • もう決まった人、もう用済みの本へのアクセス数を減らす

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'

set<ll> se[100000];
set<ll> book[100000];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    rep(i,M){
      ll K;cin>>K;
      rep(j,K){
        ll a;cin>>a;a--;
        se[a].insert(i); // aさんが関わった本はi

        book[i].insert(a);
      }
    }

    VI rank(N,-1); // 人ごとのランク
    rank[0]=0;

    VV R(N); // rankごとの人のリスト
    R[0].push_back(0); // 高橋君
    rep(i,N){
      // rank iの人たちa
      for(ll a : R[i]){
        // aさんが関わった本
        for(ll book_id : se[a]){
          for(ll b : book[book_id]){
            if(rank[b]==-1){
              rank[b]=i+1;
              R[i+1].push_back(b);
            }        
          }

          // その本については終わったので
          book[book_id].clear();
        }
      }
    }

    for(ll r : rank){
      p(r);
    }
    
    return 0;
}