Submission #7470535

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef vector<vl> mt;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<string> vs;
typedef vector<vs> table;
typedef vector<vl> v2;
typedef vector<v2> v3;
typedef vector<v3> v4;


const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 50;

ll n,m;
unordered_map<ll,vl> mp;

class union_find {
private:
  vl *par;
  vl *rnk;
  vl *siz;
public:
  union_find (ll n){
    par = new vl(n);
    iota(par->begin(),par->end(),0);
    rnk = new vl(n,0);
    siz = new vl(n,1);
  }
  ll find(ll x){
    if(par->at(x) == x) return x;
    else return par->at(x) = find(par->at(x));
  }
  ll size(ll x){
    return siz->at(find(x));
  }
  void unite(ll x,ll y){
    x = find(x);y = find(y);
    if(x == y)return;
    if(rnk->at(x) < rnk->at(y)){
      par->at(x) = y;
      siz->at(y) += siz->at(x);
    }
    else {
      par->at(y) = x;
      siz->at(x) += siz->at(y);
      if(rnk->at(x) == rnk->at(y)) rnk->at(x)++;
    }
  }
  bool same(ll x,ll y){
    return find(x) == find(y);
  }
};

union_find uf(0);

int main(){
  cin >> n >> m;
  for(ll i = 1;i <= n;i++){
    ll k;
    cin >> k;
    for(ll j = 0;j < k;j++){
      ll l;
      cin >> l;
      mp[l].push_back(i);
    }
  }
  uf = union_find(n+1);
  for(auto x : mp){
    for(ll y : x.second){
      uf.unite(x.second[0],y);
    }
  }
  if(uf.size(1) == n) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Submission Info

Judge Result