Submission #1757018

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <cstring>
#include <stack>
#include <cstdio>
#include <complex>
#include <iomanip>
#include <cctype>
#include <cassert>
#include <numeric>
#include <climits>
#include <deque>
#include <random>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int i=0;i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define show(x) cout << #x << " = " << x << endl;
#define MAX_N 100005
int par[MAX_N];
int ran[MAX_N];

void init(int n){
    rep(i,n){
        par[i] = i;
        ran[i] = 0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }else{
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    
    if(ran[x] < ran[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(ran[x] == ran[y]) ran[x]++;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}
vector<int>g[10005];
int main(){
    int n,m;
    cin >> n >> m;
    int k;
    init(n);
    rep(i,n){
        cin >> k;
        int l;
        rep(j,k){
            cin >> l;
            l--;
            g[l].push_back(i);
        }
    }
    rep(i,m){
        if(g[i].size()>=2)rep(j,g[i].size()-1){
            //cout << g[i][j] << " ";
            //cout << g[i][j] << " "<< g[i][j+1] << endl;
            unite(g[i][j],g[i][j+1]);
        }
        //cout << endl;
    }
    int same = find(0);
    rep(i,n){
        if(same != find(i)){
            cout <<"NO" << endl;
            return 0;
        }
    }
    cout <<"YES" << endl;
}

Submission Info

Judge Result