Submission #5894001

---

Source Code Expand

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

class UnionFind{
    public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> parent;

    //-1で初期化
    //最初はすべてバラバラ
    UnionFind(int N){
        parent = vector<int>(N,-1);
    }

    //Aがどのグループに属しているか(Aの根)を調べる
    int root(int A){
        if(parent[A] < 0) return A;
        return parent[A]=root(parent[A]);
    }

    //自分のいるグループの頂点数を調べる
    int size(int A){
        return -parent[root(A)];
    }

    //AとBをくっつける
    bool connect(int A, int B) {
    //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        //既にくっついているからくっつけない
        if(A == B) return false; 

        //大きいほう(A)に小さいほう(B)をくっつける
        //大証が逆ならひっくり返す
        if(size(A) < size(B)) swap(A,B);

        //Aのサイズを更新する
        parent[A] += parent[B];
        //Bの親をAに変更する
        parent[B] = A;

        return true;
    }

    //AとBが同じグループならtrueを返す
    bool same(int A, int B){
        return root(A)==root(B);
    } 
};

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);

    ll n,m;
    cin>>n>>m;
    ll k;
    vector<vector<int>> v(m);
    for(int i=0;i<n;i++){
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            a--;
            v[a].push_back(i);
        }
    }
    UnionFind uni(n);
    for(int i=0;i<m;i++){
        if(v[i].size()>1){
            int a = v[i][0];
            for(int j=1;j<v[i].size();j++){
                uni.connect(a,v[i][j]);
            }
        }
    }
    for(int i=1;i<n;i++){
        if(!uni.same(0,i)){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;



    

}

Submission Info

Judge Result