Submission #7950290

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

class UFTree
{
    vector<int> parent;
    vector<int> height;
    vector<size_t> _size;

public:
    UFTree(int size)
    {
        for (int i = 0; i < size; i++)
        {
            parent.push_back(i);
            height.push_back(0);
            _size.push_back(1);
        }
    }
    int root(int node)
    {
        if (parent[node] == node)
        {
            return node;
        }
        return parent[node] = root(parent[node]);
    }
    void merge(int n0, int n1)
    {
        int r0 = root(n0), r1 = root(n1);
        if (r0 == r1)
        {
            return;
        }
        if (height[r0] < height[r1])
            swap(r0, r1);
        if (height[r0] == height[r1])
            height[r0]++;
        parent[r1] = r0;
        _size[r0] += _size[r1];
    }
    size_t size(int node)
    {
        return _size[root(node)];
    }
};

int main()
{
    int n, m;
    cin >> n >> m;

    UFTree uft(n + m);
    vector<bool> isUsed(m, false);

    rep(i, n)
    {
        int k;
        cin >> k;
        rep(j, k)
        {
            int lang;
            cin >> lang;
            uft.merge(i, n + lang - 1);
            isUsed[lang - 1] = true;
        }
    }

    int a = count(isUsed.begin(), isUsed.end(), true);
    if (uft.size(0) == n + a)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}

Submission Info

Judge Result