CODE FESTIVAL 2016 Final: C - Interpretation

solution

人と言語で二部グラフを作って連結性判定。$O(N + M)$。

単純に全ての言語の対に辺を張ると辺数$\sum \frac{K_i (K_i-1)}{2}$で$O(N^2)$になる問題を回避すればよいということ。 なので各人$i$の母国語$L_{i1}$と第$n$言語$L_{in}$ ($n \ge 2$)と考え、母国語とそれ以外との間にだけ辺を張るでもよい。

implementation

#include <iostream>
#include <vector>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n + m);
    auto ixa = [&](int i) { return i; };
    auto ixb = [&](int i) { return n + i; };
    repeat (i,n) {
        int k; cin >> k;
        repeat (j,k) {
            int l; cin >> l; -- l;
            g[ixa(i)].push_back(ixb(l));
            g[ixb(l)].push_back(ixa(i));
        }
    }
    vector<bool> used(n + m);
    function<void (int)> go = [&](int i) {
        used[i] = true;
        for (int j : g[i]) if (not used[j]) go(j);
    };
    go(ixa(0));
    bool ans = true;
    repeat (i,n) if (not used[ixa(i)]) ans = false;
    cout << (ans ? "YES" : "NO") << endl;
    return 0;
}