MUJIN プログラミングチャレンジ C - オレンジグラフ / Orange Graph

MUJIN プログラミングチャレンジ に参加しました。企業紹介がとても面白かったです。

問題

mujin-pc-2016.contest.atcoder.jp

解法

C は「奇数長 閉路」でぐぐったら答えがわかった

— マヨ子@だがしかし可視化 (@mayoko_) 2016年2月27日

ググりましょう。すると, 奇数長の閉路がないことと, 二部グラフであることは同値であることがわかります。

ということで, グラフを 2 つに分ける様にグラフを 2 つに分けましょう。この場合分けは 2^N 通りあります。

で, 問題の条件によるとオレンジの辺はなるべくたくさん貼らないといけないので, 二部グラフ (U, W) で u U, w W について, u -> w に貼れる辺は全部貼っておきましょう。

これですべての頂点が連結だったらもう貼れる辺はなく, 連結でなかったらまだ貼れる辺があるので NG です。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<pii> G;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G.emplace_back(a, b);
    }
    set<vector<int> > S;
    for (int s = 0; s < (1<<N); s++) {
        vector<int> v;
        UnionFind uf(N);
        for (int i = 0; i < M; i++) {
            auto p = G[i];
            int a = ((s>>p.first)&1), b = ((s>>p.second)&1);
            if (a != b) {
                v.push_back(i);
                uf.unite(p.first, p.second);
            }
        }
        bool ng = false;
        for (int i = 0; i < N; i++) if (!uf.same(0, i)) ng = true;
        if (ng) continue;
        if (!v.empty()) S.insert(v);
    }
    cout << S.size() << endl;
    return 0;
}