Submission #5792688

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<int, pii> pipii;

int par[100005];
int find(int x) {
  return par[x] == x ? x : (par[x] = find(par[x]));
}
bool merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return false;
  par[x] = y;
  return true;
}

void solve() {
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) par[i] = i;
  map<int, vector<int>> dp;
  for(int i = 1; i <= n; i++) {
    int t;
    cin >> t;
    while(t--) {
      int now;
      cin >> now;
      dp[now].push_back(i);
    }
  }
  int comps = n;
  for(auto x: dp) {
    vector<int> y = x.second;
    for(int i = 1; i < y.size(); i++) comps -= merge(y[i-1], y[i]);
  }
  if(comps == 1) cout << "YES\n";
  else cout << "NO\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}

Submission Info

Judge Result