Submission #8069298

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define sz(x) ((int)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

/* O(log n) */
struct UnionFind {
  vector<int> parent;  // parent[root] is the negative of the size.
  UnionFind(int n) : parent(n, -1){};
  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v)
      return false;
    if (parent[u] > parent[v])
      swap(u, v);
    parent[u] += parent[v];
    parent[v] = u;
    return true;
  }
  bool issame(int u, int v) {
    return root(u) == root(v);
  }
  int root(int u) {
    return parent[u] < 0 ? u : parent[u] = root(parent[u]);
  }
  int size(int u) {
    return -parent[root(u)];
  }
};

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> K(N);
  vector<vector<int>> L(N);
  vector<bool> used(M, false);

  rep(i, N) {
    cin >> K[i];
    rep(j, K[i]) {
      int temp;
      cin >> temp;
      temp--;
      L[i].pb(temp);
      used[temp] = true;
    }
  }

  UnionFind U(M);
  rep(i, N) {
    rep(j, K[i] - 1) {
      U.unite(L[i][j], L[i][j + 1]);
    }
  }

  int r = -1;
  rep(i, M) {
    if (!used[i])
      continue;

    if (r == -1)
      r = U.root(i);
    else {
      if (r != U.root(i)) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  cout << "YES" << endl;
}

Submission Info

Judge Result