Submission #992270

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct UnionFind {
	vector<int> par, rank;
	int N;

	UnionFind(int n) {
		N = n;
		par.resize(n);
		rank.resize(n);

		rep(i, n) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	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;
		} else {
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

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

	int size() {
		int cnt = 0;
		rep(i, N) if(find(i) == i) cnt++;
		return cnt;
	}
};

int main() {
	int n, m;
	cin >> n >> m;

	set<int> st[m + 5];
	rep(i, n) {
		int k;
		cin >> k;

		rep(j, k) {
			int l;
			cin >> l;

			st[l].insert(i);
		}
	}

	// cout << "print set" << endl;
	// rep(i, m + 1) {
	// 	cout << i << " |";
	// 	each(it, st[i]) cout << *it + 1 << " ";
	// 	cout << endl;
	// }
	//
	UnionFind uf(n + 5);
	rep(i, m) {
		if(st[i+1].size() <= 1) continue;
		int pre = *(st[i+1].begin());
		each(it, st[i+1]) {
			uf.unite(pre, *it);
		}
	}

	int cnt = 0;
	rep(i, n) {
		if(uf.find(0) == uf.find(i)) cnt++;
	}

	if(cnt == n) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Submission Info

Judge Result