Submission #993012

---

Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 100000000;
using namespace std;


const int gmax_n = 100000;

int par[gmax_n]; //親
int kRank[gmax_n];//木の深さ

void init(int n){
    rep(i,n){
        par[i] = i;
        kRank[i] = 0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(kRank[x] < kRank[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(kRank[x] == kRank[y]) kRank[x]++;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

int main(){
    int n, m;
    cin >> n >> m;
    init(n);


    vector<vector<int>> v(m + 1); //ls[i] : iの言語を話せる人の番号
    rep(i,n){
        int k;
        cin >> k;
        rep(j,k){
            int l;
            cin >> l;
            v[l].emplace_back(i);
        }
    }

    range(i,1,m + 1){
        /*
        show(i)
        rep(j,v[i].size()){
            cout << v[i][j] << endl;
        }
        cout << endl;
        */
        if(v[i].size() <= 1) continue;
        rep(j,v[i].size() - 1){
            unite(v[i][j], v[i][j + 1]);
        }
    }

    int cnt = 0;
    rep(i,n) if(par[i] == i) cnt++;
    //rep(i,n) { debug(par[i]) }
    if(cnt > 1) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Submission Info

Judge Result