Submission #991812

---

Source Code Expand

/* -------------------------------- Template -------------------------------- */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

template<typename T> constexpr T inf = [](){ assert(false); };
// template<> constexpr int inf<int> = 1e9;
// template<> constexpr ll inf<ll> = 1e18;
// template<> constexpr ld inf<ld> = 1e30;

struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve();

int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}

using namespace std;

/* -------------------------------- Library -------------------------------- */

class UnionFind {
  vector<int> p;
  int sz;
public:
  UnionFind (int n) : p(n, -1), sz(n) {}
  int root(int x) {
    return p[x] < 0 ? x : p[x] = root(p[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    --sz;
    return true;
  }
  int size() const { return sz; }
};

/* ---------------------------------- Main ---------------------------------- */

void solve() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> m(M);
  REP(i,N) {
    int K, L; cin >> K;
    REP(j,K) {
      cin >> L; --L;
      m[L].push_back(i);
    }
  }
  UnionFind uf(N);
  REP(i,M) {
    const int n = m[i].size();
    REP(j,n-1) {
      uf.unite(m[i][j], m[i][j+1]);
    }
  }
  cout << (uf.size() == 1) << endl;
  return;
}

Submission Info

Judge Result