Submission #992219

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

constexpr int MAX = 100000;

class Union_Find {
  public:
    int par[MAX], rank[MAX], size[MAX], gnum;
    
    Union_Find(int N) {
        gnum = N;
        for (int i = 0; i < N; i++) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    int find(int x)
    {
        if (par[x] == x) {
            return x;
        }
        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;
            size[y] += size[x];
        } else {
            par[y] = x;
            size[x] += size[y];
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
        gnum--;
    }

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

    int getSize(int x)
    {
        return size[find(x)];
    }

    int groups()
    {
        return gnum;
    }
};

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> G[MAX];
    Union_Find uf(N);
    for (int i = 0; i < N; i++) {
        int K;
        cin >> K;
        for (int j = 0; j < K; j++) {
            int L;
            cin >> L; --L;
            for (auto& g : G[L]) {
                uf.unite(g, i);
            }                
            G[L].emplace_back(i);
        }
    }
    cout << (uf.groups() == 1 ? "YES" : "NO") << endl;
    return 0;
}

Submission Info

Judge Result