Submission #992159

---

Source Code Expand

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
//#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

struct UFT{ //O(loga(n))
    int n;
    vi d, r;
    UFT(int n) : n(n), d(n, -1), r(n, 0){};
    int root(int i){
        if(d[i] < 0) return i;
        return d[i] = root(d[i]);
    }
    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(r[x] < r[y]) swap(x, y);
        else if(r[x] == r[y]) r[x]++;
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    int size(int i){
        return -d[root(i)];
    }
};

int main(){
	int n, m;
	cin>>n>>m;
	map<int, int> mp;
	UFT u(1e5+10);
	rep(i, n){
		int k;
		cin>>k;
		rep(j, k){
			int l;
			cin>>l;
			if(mp.count(l)){
				u.unite(mp[l], i);
			}
			else{
				mp[l] = i;
			}
		}
	}
	cout<<(u.size(0)==n?"YES":"NO")<<endl;
}

Submission Info

Judge Result