不思議マーケット [yukicoder No.679] - はまやんはまやんはまやん

考察

1. 全探索はできない
2. DPかフローというのもありそう
3. ★2.5なので、もうちょっと単純にできないか
4. 貪欲でいいのでは？

解法

貪欲法で解く。
かごに入れることができるものから順番に商品を置いていくことにする。
　
かごに入れるための関係性は有向グラフとして考えることができる。
頂点：商品
　辺：依存関係 h[i][j]からg[i]に辺をはる
この有向グラフから入次数が0の頂点を貪欲に消していくことを考える。
頂点を消したら、そこから出ている辺は全て消す。
すると入次数が0の頂点が増える可能性があるので、もしあるなら、それも消していく。
　
この実装はqueueを使ってやるといい。
この手の貪欲はよく見かけるので、実装練習をしておこう。

int N, M, R[505];
vector<int> E[505];
int cnt[505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(m, 0, M) {
        int g; cin >> g; g--;
        cin >> R[g];
        rep(i, 0, R[g]) {
            int x;
            cin >> x;
            x--;
            E[x].push_back(g);
        }
    }

    int ans = 0;
    queue<int> qu;
    rep(i, 0, N) if (cnt[i] == R[i]) qu.push(i);
    while (!qu.empty()) {
        int cu = qu.front();
        qu.pop();
        ans++;

        fore(to, E[cu]) {
            cnt[to]++;
            if (cnt[to] == R[to]) qu.push(to);
        }
    }

    cout << ans << endl;
}