Submission #7499017

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

struct edge{int to, from;};

struct UnionFind
{
    vector<int> rank;
    vector<int> parent;
    const int n;
    UnionFind(int _n) :n(_n)
    {
        rank.assign(n, 1);
        parent.assign(n, -1);
    }

    int find(int node)
    {
        assert (node < n);

        if (parent[node] == -1)
            return node;
        else
            return parent[node] = find(parent[node]);
    }

    void unite(int i, int j)
    {
        i = find(i);
        j = find(j);

        if (i == j)
            return;

        if (rank[i] == rank[j])
        {
            parent[j] = i;
            rank[i]++;
        }
        else
        {
            if (rank[i] > rank[j]) swap(i, j);
            parent[j] = i;
        }
    }

    bool is_same(int i, int j)
    {
        return find(i) == find(j);
    }
};

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

    vector<edge> E;
    rep(i, 0, n)
    {
        int k;
        cin >> k;
        rep(j, 0, k)
        {
            int lang;
            cin >> lang;
            --lang;
            edge ee = {i, n+lang};
            E.push_back(ee);
        }
    }

    UnionFind uf(n+m);
    for (edge e: E)
        uf.unite(e.to, e.from);

    bool ans = true;
    rep(i, 0, n)
        ans &= uf.is_same(0, i);

    if (ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Submission Info

Judge Result