Submission #2343597

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define REPS(i,n) for(int i=1;i<=(n);i++)
#define RREPS(i,n) for(int i=(n);i>0;i--)
#define mp make_pair
#define pb(a) push_back(a)
typedef long long ll;
#define MAX_N 100000
int parent[MAX_N],r[MAX_N];

void Makeset(int n){
    REP(i,n){
        parent[i] = i;
        r[i] = 0;
    }
}

int Find(int x){
    if(parent[x] == x) return x;
    else{
        return parent[x] = Find(parent[x]);
    }
}

void Union(int x,int y){
    int xroot = Find(x);
    int yroot = Find(y);
    if(xroot == yroot) return;
    if(r[x] < r[y]){
        parent[xroot] = yroot;
    }else{
        parent[yroot] = xroot;
        if(r[xroot] == r[yroot]) r[xroot]++;
    }
}

bool isUnion(int x,int y){
    if(Find(x) == Find(y)) return true;
    else return false;
}
vector<int> v[MAX_N];
int main(){
  int N,M;
  cin >> N >> M;
  Makeset(N);
  REP(i,N){
    int K;
    cin >> K;
    REP(j,K){
      int L;
      cin >> L;
      v[L-1].pb(i);
    }
  }
  REP(j,M){
    REPS(i,(int)v[j].size()-1){
      Union(v[j][i-1],v[j][i]);
    }
  }
  bool ans = true;
  REPS(i,N-1){
    if(! isUnion(0,i)){
      ans = false;
      break;
    }
  }
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Submission Info

Judge Result