Submission #992888

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
using namespace std;
class UnionFind {
  vector<int> p;
public:
  UnionFind (int n) : p(n, -1) {}
  int root(int x) {
    return p[x] < 0 ? x : p[x] = root(p[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};
 
int main(void)
{
  int n,m;
  cin >> n >> m;
  UnionFind uf(n);
  vector<int> la(m+1,-1);
  int answer=1;
  REP(i,n){
    int k;
    cin >> k;
    REP(j,k){
      int l;
      cin >> l;
      if(la[l]!=-1) if(uf.unite(la[l], i)) ++answer;
      la[l]=i;
    }
  }
  cout << (answer==n ? "YES" : "NO") << endl;
  return 0;
}

Submission Info

Judge Result