Submission #991717

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

const int N = (int) 1e5;
vector<int> whoSpeak[N];
int lab[N];

int get(int u) {
    return lab[u] < 0 ? u : lab[u] = get(lab[u]);
}

void join(int u, int v) {
    u = get(u); v = get(v);
    if (u == v) return;
    if (lab[u] < lab[v]) swap(u, v);
    lab[v] += lab[u];
    lab[u] = v;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int k; cin >> k;
        for (int j = 0; j < k; ++j) {
            int l; cin >> l; --l;
            whoSpeak[l].push_back(i);
        }
    }
    for (int i = 0; i < n; ++i) lab[i] = -1;
    for (int l = 0; l < m; ++l) {
        for (int i = 1; i < (int) whoSpeak[l].size(); ++i) {
            join(whoSpeak[l][0], whoSpeak[l][i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (get(i) != get(0)) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Submission Info

Judge Result