Submission #992068

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1000000007;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;
typedef long long ll;

class UnionFind{
public:
    vector<int> par;
    vector<int> rank;
    UnionFind(int n){
        init(n);
    }
    void init(int n){
        par.resize(n);
        for(int i=0;i<n;i++){
            par[i] = i;
        }
        rank.assign(n, 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(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

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 lang;
            cin >> lang;
            uf.unite(i, N + lang - 1);
        }
    }

    for(int i=0;i<N;i++){
        if(!uf.same(0, i)){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Submission Info

Judge Result