Submission #2362029

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) {}
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

int main() {
  int N, M;
  while (cin >> N >> M) {
    UnionFind uf(N + M);
    for (int i = 0; i < N; i++) {
      int K;
      cin >> K;
      for (int j = 0; j < K; j++) {
        int L;
        cin >> L;
        --L;
        uf.unionSet(i, N + L);
      }
    }
    bool res = true;
    for (int i = 1; i < N; i++) res &= uf.findSet(0, i);
    cout << (res ? "YES" : "NO") << endl;
  }
  return 0;
}

Submission Info

Judge Result