Submission #992444

---

Source Code Expand

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

const int MAX_N = 100000;
class UnionFind {
private:
    int union_size[MAX_N];
    int rank[MAX_N];

public:
    int par[MAX_N];
    
    void init(int n)
    {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
            union_size[i] = 1;
        }
    }
    
    // 木の根を求める
    int find(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    
    // xとyの属する集合を併合する
    void merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y) return;

        union_size[x] += union_size[y];
        union_size[y] = union_size[x];

        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }
    
    // xとyが同じ集合に属するか判定する
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    
    // x が含まれる集合の要素数を返す
    int getUnionSize(int x)
    {
        return union_size[find(x)];
    }
};

int main()
{
    ios::sync_with_stdio(false);

    map<int, set<int>> can;

    int N, M;
    cin >> N >> M;
    rep(i, N) {
        int K; cin >> K;
        rep(j, K) {
            int L;
            cin >> L;
            L--;
            can[L].insert(i);
        }
    }

    UnionFind UF;
    UF.init(N);

    rep(i, M) {
        if (can[i].size() == 0) continue;
        for (auto u : can[i]) {
            UF.merge(i, u);
        }
    }

    cout << (UF.getUnionSize(0) == N ? "YES" : "NO") << endl;
}

Submission Info

Judge Result