Submission #1406939

---

Source Code Expand

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>

#ifdef _MSC_VER
#include <Windows.h>
#else
#include <unistd.h>
#endif

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD=(LL)1e9+7;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

#define INF 1LL << 50

struct UnionFind
{
    vector<int> par;
    vector<int> sizes;

    UnionFind(int n) : par(n), sizes(n, 1) {
        REP(i,n) par[i] = i;
    }

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

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

    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return sizes[find(x)];
    }
};
vector<LL>L[(int)1e5+2];
int main(){
    int N,M;
    cin>>N>>M;
    
    REP(i,N){
        int K;
        cin>>K;
        REP(j,K){
            int l;
            cin>>l;l--;
            L[l].PB(i);
        }
    }
    UnionFind uf(N);
    REP(i,M)FOR(j,1,SZ(L[i])){
        uf.unite(L[i][j],L[i][0]);
    }
    if(uf.size(0)==N){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Submission Info

Judge Result