Submission #7954991

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T> inline T divrup(T a, T b) { if (a % b) return a/b+1; else return a/b;}

#define dbg_v1(i,V) do{cout<<"-v1----\n";rep(i,V.size())cout<<" "<<i<<"\t:"<<V[i]<<endl;cout<<endl;}while(0)
#define dbg_v2(i,k,V) do{cout<<"-v2----\n";rep(i,V.size()){rep(k,V[0].size())cout<<" "<<V[i][k];cout<<endl;}}while(0)

// Union-Find木
template<class Abel>//加減可能のアーベル群
class UnionFind{
protected:
    vector<int> par;//親ノード
    vector<Abel> pod;//ポテンシャル
    Abel O=0;
public:
    UnionFind(int n,Abel zero=0) : par(n,-1),pod(n,zero){
        O=zero;
    }

    //根を求める（同時に経路圧縮）
    int root(int x){
        if(par[x]<0) return x;
        int r = root(par[x]);
        pod[x] +=pod[par[x]];
        return par[x]=r;
    }

    //根が等しいか判定
    bool issame(int x,int y){
        return root(x)==root(y);
    }

    //マージ
    bool unite(int base,int x){
        unite(base,x,O);
    }
    bool unite(int base,int x,Abel pd){
        pd -=p(x) - p(base);
        base=root(base);x=root(x);
        if(base==x)return false;
        if(par[base]>par[x]) std::swap(base,x),pd=-pd;
        //baseがxの親になる
        par[base] +=par[x];//根は-(size)
        par[x]=base;
        pod[x]=pd;
        return true;
    }

    //属す根のサイズ
    int size(int x){
        return -par[root(x)];
    }
    //要素のポテンシャル
    Abel p(int x){
        root(x);//経路圧縮
        return pod[x];
    }
    //要素の相対ポテンシャル
    Abel diff(int base,int x){
        if(issame(base,x)) return pod[x]-pod[base];
        return 0;//同箇所にない場合は未定義
    }
};


int main() {
    ios::sync_with_stdio(false);//stdoutとcoutの同期解除
    cin.tie(nullptr);//cinとcoutの同期解除
    
    int N,M,K,L;
    cin >>N>>M;
    
    UnionFind<int> COMU(N+M,0);
    rep(i,N){
        cin>>K;
        rep(k,K){
            cin>>L;
            COMU.unite(i,N+L-1);
        }
    }
    bool is=true;
    repd(i,1,N){
      is=(is &&COMU.issame(i-1,i));
    }

    cout << ((is) ? "YES" : "NO") <<endl;
    return (0);
}

Submission Info

Judge Result