CODE FESTIVAL 2016 Final C - Interpretation

問題概要

C - Interpretation

解法

愚直に全ての人の間に辺を貼ろうとすると$O(N^2)$となるため間に合わない。そこで、人$i$と言語$L_{ij}$の二部グラフを作り、人$i$が話せる言語$L_{ij}$に対して辺を貼る。このグラフにおいて、全ての人が連結であれば答えはYES、連結でなければ答えはNO。連結判定にはUnionFind等を使えばよい。計算量は$O(N + M)$で十分高速である。

ソースコード

#include <bits/stdc++.h>

using namespace std;

#define llong long long int
#define ldouble long double
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)

const static llong MOD = 1000000000 + 7;
const static llong INF = 1LL << 60;
const static double eps = 1e-6;
const static int dy[] = {0, 1, 0, -1};
const static int dx[] = {1, 0, -1, 0};

template<typename T> T my_gcd(T a, T b) {
    return (a ? my_gcd(b % a, a) : b);
}

template<typename T> T my_lcm(T a, T b){
	return a * b / my_gcd(a, b);	
}

template<typename T> struct UF {
    vector<int> par;
    vector<T> sz;

    UF(int n) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_root(int x) {
        return par[x] == x ? x : par[x] = find_root(par[x]);
    }

    bool same(int x, int y) {
        return find_root(x) == find_root(y);
    }

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

    T size_of_tree(int x) {
        return sz[find_root(x)];
    }
};

signed main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    UF<int> uf(n + m);
    rep(i, n) {
        int k;
        cin >> k;
        rep(j, k) {
            int l;
            cin >> l;
            uf.unite(l - 1, m + i);
        }
    }

    bool flag = true;
    rep(i, n - 1) {
        if (! uf.same(m + i, m + i + 1)) {
            flag = false;
            break;
        }
    }

    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}