Submission #5433888

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct unionFind {
  int n;
  vector<int> pr;

  unionFind(){};
  unionFind(int _n) {
    n = _n;
    pr.resize(n, -1);
  };
  int root(int a) {
    if (pr[a] == -1)
      return a;
    else
      return pr[a] = root(pr[a]);
  }
  void unify(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return;
    pr[a] = b;
  }
  int same(int a, int b) { return root(a) == root(b); }
};

signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> k(n);
  vector<vector<int>> l(n);
  vector<bool> used(m, false);

  for (int i = 0; i < n; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      int x;
      cin >> x;
      x--;
      l[i].push_back(x);
    }
  }

  unionFind uf(m);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k[i]; j++) {
      used[l[i][j]] = true;
      uf.unify(l[i][0], l[i][j]);
    }
  }
  int r = uf.root(l[0][0]);

  for (int i = 0; i < m; i++) {
    if (used[i]) {
      if (r != uf.root(i)) {
        cout << "NO" << endl, exit(0);
      }
    }
  }
  cout << "YES" << endl;
}

Submission Info

Judge Result