Submission #6857962

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()

struct UnionFind {
  vector<int> par;
  vector<int> sizes;

  UnionFind(int N) : par(N), sizes(N, 1) {
    for(int i = 0; i < N; i++) par.at(i) = i;
  }

  int find(int x) { 
    if (par.at(x) == x) return x;
    return par.at(x) = find(par.at(x));
  }

  void unite(int x, int y) {
    int rx = find(x); 
    int ry = find(y); 
    if (rx == ry) return; 
    if (sizes.at(rx) < sizes.at(ry)) swap(rx,ry);
    par.at(ry) = rx;
    sizes.at(rx) += sizes.at(ry);    
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  int size(int x){
    return sizes.at(find(x));
  }

  int num_of_connected_components(){
    int ret = 0;
    for(int i = 0; i < par.size(); i++){
      if(find(i) == i) ret++;
    }
    return ret;
  }
};

int main(){
  ll n,m; cin >> n >> m;
  UnionFind uft(n);
  vector<vector<ll>> lang(m);
  REP(i,n){
    ll k; cin >> k;
    REP(j,k){
      ll l; cin >> l;
      l--;
      lang[l].push_back(i);
    }
  }
  REP(i,m){
    ll s = lang[i].size();
    if(s<2) continue;
    FOR(j,1,s){
      uft.unite(lang[i][0], lang[i][j]);
    }
  }
  if(uft.num_of_connected_components()==1) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Submission Info

Judge Result