Submission #993139

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) { // size(x) > size(y)
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

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

    int size(int x) {
        return -par_[root(x)];
    }

private:
    std::vector<int> par_;
};

int main() {
    int N, M;
    cin >> N >> M;
    union_find uf(N);
    vector<vector<int>> l(M+1);
    for(int i=0; i<N; ++i) {
        int K=0;
        cin >> K;
        for(int j=0; j<K; ++j) {
            int L;
            cin >> L;
            L--;
            l[L].push_back(i);
        }
    }
    for(int i=0; i<l.size(); ++i) {
        for(int j=1; j<l[i].size(); ++j) {
            uf.unite(l[i][j], l[i][j-1]);
        }
    }
    for(int i=0; i<N-1; ++i) {
        if(!uf.same(i, i+1)) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

Submission Info

Judge Result