Submission #992595

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef vector<int, int> VII;
typedef vector<int> VI;
typedef pair<int, int> PII;

const int MAX_N = 1e6 + 5;
int par[MAX_N];

void init(int n) {
  for (int i = 0; i < n ; i++) {
    par[i] = i;
  }
}

int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  par[x] = y;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  init(N);
  VI ps;
  for (int i = 0; i < M; i++) {
    ps.push_back(-1);
  }

  for (int i = 0; i < N; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int n;
      cin >> n;
      n--;
      if (ps[n] == -1) {
        ps[n] = i;
      }
      merge(ps[n], i);
    }
  }

  for (int i = 0; i < N-1; i++) {
    if (!same(i, i+1)) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  return 0;
}

Submission Info

Judge Result