Submission #992294

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      5000000000000000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;

struct UF{
	int par[100000];
	int rank[100000];
	int si[100000];

	void init(int n){
		rep(i,n){
			par[i] = i;
			rank[i] = 0;
			si[i] = 1;
		}
	}

	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
			si[y] += si[x];
		} else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
			si[x] += si[y];
		}
	}

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

int n, m;
int k;
UF uf;
vector<int> e[100000];

int main(){
    cin >> n >> m;
    uf.init(n);
    rep(i,n){
        int k;
        cin >> k;
        rep(j,k){
            int m;
            cin >> m;
            m--;
            e[m].push_back(i);
        }
    }
    rep(i,m){
        for(int j = 1; j < e[i].size(); j++){
            uf.unite(e[i][0],e[i][j]);
        }
    }
    int cnt = 0;
    rep(i,n){
        if(uf.par[i] == i){
            cnt++;
        }
    }
    if(cnt > 1) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Submission Info

Judge Result