Submission #6444610

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

struct UnionFind {
    vector<int> rank, parent, size;

    // +1 for 1-indexed nodes
    UnionFind(int n) : rank(n + 1, 0), parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0); // parent is itself
    }
    int root(int x) {
        if (x != parent[x]) {
            parent[x] = root(parent[x]);
        }
        return parent[x];
    }
    bool isSame(int x, int y) { return root(x) == root(y); }
    bool unite(int x, int y) { return link(root(x), root(y)); }
    bool link(int x, int y) {
        if (x == y)
            return false;
        if (rank[x] > rank[y]) {
            parent[y] = x;
            size[x] += size[y];
        } else {
            parent[x] = y;
            size[y] += size[x];
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
        return true;
    }
    int getSize(int x) { return size[root(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vi k(n);
    vvi l(n);
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
        l[i].resize(k[i]);
        for (int j = 0; j < k[i]; ++j) {
            cin >> l[i][j];
        }
    }
    UnionFind uf(n + m);
    for (int i = 0; i < n; ++i) {
        for (auto &lang : l[i]) {
            uf.unite(i, n + lang - 1);
        }
    }
    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (!uf.isSame(i, 0)) {
            ok = false;
            break;
        }
    }
    if (ok)
        cout << "YES"
             << "\n";
    else
        cout << "NO"
             << "\n";

    return 0;
}

Submission Info

Judge Result