Submission #7372368

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct UnionFind{
    vector<int> par;
    
    UnionFind(int n) : par(n,-1) { }
    void init(int n) { par.assign(n,-1); }
    
    int root(int x){
        if(par[x]<0) return x;
        else return par[x]=root(par[x]);
    }
    
    bool issame(int x,int y){
        return root(x)==root(y);
    }
    
    bool merge(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(par[x]>par[y]) swap(x,y);
        par[x]+=par[y];
        par[y]=x;
        return true;
    }
    
    int size(int x){
        return -par[root(x)];
    }
};



int main(){
    int n,m;
    cin>>n>>m;
    UnionFind uf(n+m);
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int l;
            cin>>l;
            uf.merge(l-1,m+i);
        }
    }

    for(int i=0;i<n-1;i++){
        if(!uf.issame(m+i,m+i+1)){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
}

Submission Info

Judge Result