Submission #7046579

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%mood;
		x = x * x%mood;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n, m, k, l;

class Union_Find {
private:
	int par[200010], rank[200010];
public:
	void init(int n) {
		for (int i = 1; i <= n; i++) {
			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);
	}
};

signed main() {
	cin >> n >> m;
	Union_Find ta;
	ta.init(n + m);
	for (int i = 0; i < n; i++) {
		cin >> k;
		for (int j = 0; j < k; j++) {
			cin >> l;
			ta.unite(i + 1, n + l);
		}
	}
	for (int i = 1; i < n; i++) {
		if (!ta.same(i, i + 1)) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}

Submission Info

Judge Result