Submission #5824363

---

Source Code Expand

#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

class Union_Find {
    public:
    std::vector<int> par;
    Union_Find() {}
    Union_Find(int n){
        par.resize(n, 0);
        for(int i = 0; i < n; i++){
            par[i] = i;
        }
    }

    void simplify(int x) {
        std::vector<int> path;
        while (par[x] != x) {
            path.push_back(x);
            x = par[x];
        }
        for (int p : path) {
            par[p] = x;
        }
    }
    
    int find(int x){
        simplify(x);
        return par[x];
    }
    
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if (x != y) {
            par[y] = x;
            // 改造する時は「根になっているノードの親を変更する」という原則が守られていることに注意。
        }
    }
};

const int MAX = 100050;
const int MAX_N = 200050;
const int MAX_K = 100050;

int N, M;
int K[MAX];
std::vector<int> L[MAX];

Union_Find uf = Union_Find(MAX * 2);

int main(int argc, char **argv) {
    std::cin >> N >> M;

    int tmp;
    for (int i = 1; i <= N; i++) {
        std::cin >> K[i];
        for (int j = 1; j <= K[i]; j++) {
            std::cin >> tmp;
            L[i].push_back(tmp);
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j : L[i]) {
            uf.unite(i, N + j);
        }
    }

    for (int i = 1; i <= N; i++) {
        if (uf.find(i) != uf.find(1)) {
            std::cout << "NO" << std::endl;
            return 0;
        }
    }

    std::cout << "YES" << std::endl;

    return 0;
}

Submission Info

Judge Result