Submission #992009

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

class UFT {
  vector<int> parent;
  vector<int> rank; //木の高さ
  vector<int> size;
public:
  UFT(int n){
    parent = vector<int>(n);
    rank = vector<int>(n,0);
    size = vector<int>(n,1);
    for(int i = 0; i < n; i++)
      parent[i] = i;
  }
  int find_root(int x){
    if ( parent[x] == x ) return x;
    return parent[x] = find_root( parent[x] );
  }
  void unite(int x, int y){
    int u = find_root(x);
    int v = find_root(y);
    if ( u == v ) return;
    if ( rank[u] < rank[v] ){
      parent[u] = v;
      size[v] += size[u];
    }else{
      parent[v] = u;
      size[u] += size[v];
      if ( rank[u] == rank[v] ) rank[x]++;
    }
  }
  bool is_same ( int x, int y ){
    return find_root(x) == find_root(y);
  }
  int size_of ( int x ){
    return size[ find_root(x) ];
  }
};

int N, M;
int K[100000];
set<int> L;
vector<int> l[100000];
int main(){
  cin >> N >> M;
  UFT uft(M);
  REP(i,N){
    cin >> K[i];
    REP(j,K[i]){
      int t;
      cin >> t;
      t--;
      l[i].push_back( t );
      L.insert( t );
      if( j > 0 ){
	uft.unite( l[i][0], l[i][j] );
      }
    }
  }
  if( uft.size_of( l[0][0] ) == L.size() ){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Submission Info

Judge Result