Submission #991902

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long ll;
typedef pair<ll,ll> P;
const int INF=INT_MAX / 3;
const ll LINF=LLONG_MAX / 3LL;
#define CONST 1000000007
#define EPS (1e-8)
#define PB push_back
#define MP make_pair
#define sz(a) ((int)(a).size())
#define reps(i,n,m) for(int i=(n);i<int(m);i++)
#define rep(i,n) reps(i,0,n)
#define SORT(a) sort((a).begin(),(a).end())
ll mod(ll a,ll m){return (a%m+m)%m;}
int dx[9]={0,1,0,-1,1,1,-1,-1,0},dy[9]={1,0,-1,0,1,-1,1,-1,0};
typedef vector<int> VI;
typedef vector<VI> VVI;

struct unionFind {
  VI par, rank;
  int n;
  void init(int x) {
    n = x;
    par.resize(n);
    rank.resize(n);
    rep(i,n) {
      par[i] = i;
      rank[i] = 0;
    }
  }
  int root (int x) {
    if (par[x] == x) {
      return x;
    }
    return par[x] = root(par[x]);
  }
  bool same (int x, int y) {
    return root(x) == root(y);
  }
  void unite (int x, int y) {
    x = root(x);
    y = root(y);
    if (x==y) return;
    if(rank[x]<rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if(rank[x]==rank[y]) rank[x]++;
    }
  }
  int treeNum () {
    set<int> s;
    rep(i,n) {
      s.insert(root(i));
    }
    return s.size();
  }
};

ll n,m;
int main(){
  cin>>n>>m;
  unionFind uf;
  uf.init(n + m);
  rep(i,n){
    int k;
    cin>>k;
    rep(j,k){
      int l;
      cin>>l;
      uf.unite(i, n+l-1);
    }
  }
  bool flg=true;
  rep(i,n){
    if(!uf.same(0,i))flg=false;
  }
  cout<<(flg?"YES":"NO")<<endl;
  return 0;
}

Submission Info

Judge Result