Submission #1775524

---

Source Code Expand

#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
class unionfind {
    vector<int> par, rank, size_;//速度ではなくメモリ効率を考えるならrankのかわりにsizeを使う
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(all(par), 0);
    }
    int find(int x) {
        if (par[x] == 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 (rank[x] < rank[y])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};
signed main(){
    int n,p; cin>>n>>p;
    vector<vector<int>>v(n,vector<int>());
    unionfind uni(p+1);
    rep(i,n){
        int k; cin>>k;
        rep(j,k){
            int temp; cin>>temp;
            v[i].push_back(temp);
        }
    }
    map<int, int>Mp;
    int key=v[0][0];
    rep(i,v[0].size())uni.unite(key,v[0][i]);
    rep(i,n){
        bool in=false;
        rep(j,v[i].size()){
            if(uni.same(key,v[i][j])){
                in=true;
                break;
            }
        }
        if(in)rep(j,v[i].size())uni.unite(key,v[i][j]);
        else Mp[v[i][0]]++;
    }
    bool ans=true;
    rep(i,n){
        bool in=false;
        rep(j,v[i].size()){
            if(uni.same(key,v[i][j])){
                in=true;
                break;
            }
        }
        if(in)rep(j,v[i].size())uni.unite(key,v[i][j]);
        else ans=false;
    }
    cout<<(ans?"YES":"NO")<<endl;
}

Submission Info

Judge Result