Submission #992874

---

Source Code Expand

#include <iostream>
#include <vector>

unsigned search (std::vector<unsigned> &group, unsigned index) {
  if (group[index] == index) {
    return index;
  }
  return group[index] = search(group, group[index]);
}

int main() {
  unsigned N, M, K;
  std::cin >> N >> M;
  std::vector<unsigned> group(M + 1);
  std::vector<bool> use(M + 1, false);
  for (unsigned i = 0; i <= M; ++i) {
    group[i] = i;
  }
  std::vector<unsigned> buf(100000);
  for (unsigned i = 0; i < N; ++i) {
    std::cin >> K;
    unsigned min = UINT32_MAX;
    for (unsigned j = 0; j < K; ++j) {
      std::cin >> buf[j];
      min = std::min(search(group, buf[j]), min);
      use[buf[j]] = true;
    }
    for (unsigned j = 0; j < K; ++j) {
      if (group[buf[j]] != min) {
        group[group[buf[j]]] = min;
      }
    }
  }
  for (unsigned i = 1; i <= M; ++i) {
    if (use[i] && group[i] != 1) {
      std::cout << "NO";
      return 0;
    }
  }
  std::cout << "YES";
  return 0;
}

Submission Info

Judge Result