Submission #992445

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;


template<typename T>
class UF
{
public:
	UF() {
		size = 0;
	}

	//値を挿入する
	void push( T a ) {
		M[a] = size;
		V.push_back( size );
		rank.push_back( 0 );
		C.push_back( 1 );
		size++;
	}

	//同じグループにする
	void unite( T a, T b ) {
		long long int x = find( M[a] );
		long long int y = find( M[b] );
		if( x == y )return;
		if( rank[x] < rank[y] ) {
			V[x] = y;
			C[y] += C[x];
		} else {
			V[y] = x;
			C[x] += C[y];
			if( rank[x] == rank[y] )rank[x]++;
		}
	}

	void merge( T a, T b ) {
		unite( a, b );
	}

	//同じグループにいるかどうか判定する
	bool same( T a, T b ) {
		return find( M[a] ) == find( M[b] );
	}

	//今何グループあるか数を返す
	long long int group() {
		set<long long int >S;
		for( long long int i = 0; i < V.size(); i++ ) {
			S.insert( find( V[i] ) );
		}
		return S.size();
	}

	//グループに属している数を返す
	long long int count( T a ) {
		return C[find( M[a] )];
	}

private:
	vector<long long int>
		C, V, rank;
	map < T, long long int>M;
	long long int size;

	//祖先までたどる
	long long int find( long long int x ) {
		if( V[x] == x )return x;
		else return V[x] = find( V[x] );
	}
};



int main() {
	UF<long long int>uf;
	long long int N, M;
	cin >> N >> M;
	for( size_t i = 0; i < N + M; i++ ) {
		uf.push( i );
	}
	for( size_t i = 0; i < N; i++ ) {
		long long int K;
		cin >> K;
		for( size_t j = 0; j < K; j++ ) {
			long long int L;
			cin >> L;
			L--;
			uf.merge( i, L + N );
		}
	}
	bool f = true;
	for( size_t i = 1; i < N; i++ ) {
		f = f&&uf.same( 0, i );
	}
	cout << (f ? "YES" : "NO") << endl;
}

Submission Info

Judge Result