TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Pair of Balls

問題

D – Pair of Balls
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// 22:09

int main() {
  int N, M;
  cin >> N >> M;

  vector<queue<int>> a(M);

  // 取れるボール
  vector<vector<int>> Ball(N);
  rep(i, M) {
    int k;
    cin >> k;
    rep(j, k) {
      int a2;
      cin >> a2;
      a2--;
      a[i].push(a2);
    }
    Ball[a[i].front()].push_back(i);
  }

  // 2個取れるボール
  queue<int> que;

  rep(i, N) {
    if (Ball[i].size() == 2) {
      que.push(i);
    }
  }

  while(!que.empty()) {
    int c = que.front();
    que.pop();
    for(auto i : Ball[c]) {
      a[i].pop();
      if (!a[i].empty()) {
        Ball[a[i].front()].push_back(i);
        if (Ball[a[i].front()].size() == 2) {
          que.push(a[i].front());
        }
      }
    }
  }

  rep(i, M) {
    if(!a[i].empty()) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}