AOJ 1388 - Counting Cycles

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1388

解法

m <= n + 15 なので、サイクル基底を考えれば高々 2^16 通りしかないことがわかる。
つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。

サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。
よく考えると、次数が 2 以下の頂点は縮約なり削除しても結果に影響しないことがわかる。
これによって、頂点数（辺の数）は k = m - n + 1 として 2k 程度に落ちることがわかる。
ここまで小さくなれば、愚直に探索しても十分間に合う。
注意点は以下の通り。

• 同じサイクルを重複して数えないようにする
  • 残った辺に id を割り振って、使った辺集合を bit で管理して set に入れると楽
• 自己ループ、多重辺
  • グラフ圧縮の過程で発生する
  • 自己ループが発生してる頂点は変に削除すると数え漏れが起こるので注意（実装依存）
  • 多重辺は、辺に固有 id を割り振っておいて区別すれば OK

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using graph = vector<set<pii>>;

void compress_graph(graph& g, int& uid) {
    const int n = g.size();
    queue<int> que;

    // remove leaves
    for(int v = 0; v < n; ++v) {
        if(g[v].size() == 1u) {
            que.push(v);
        }
    }
    while(!que.empty()) {
        const int v = que.front();
        que.pop();
        if(g[v].size() != 1u) continue;
        const auto e = *g[v].begin();
        g[v].clear();
        g[e.first].erase(make_pair(v, e.second));
        if(g[e.first].size() == 1u) {
            que.push(e.first);
        }
    }

    // constraction
    for(int v = 0; v < n; ++v) {
        if(g[v].size() == 2u) {
            que.push(v);
        }
    }
    while(!que.empty()) {
        const int v = que.front();
        que.pop();
        if(g[v].size() != 2u) continue;
        const int a = g[v].begin()->first, a_uid = g[v].begin()->second;
        const int b = next(g[v].begin())->first, b_uid = next(g[v].begin())->second;
        if(a == b) continue; // self-loop
        g[v].clear();
        g[a].erase(make_pair(v, a_uid));
        g[b].erase(make_pair(v, b_uid));
        ++uid;
        g[a].emplace(b, uid);
        g[b].emplace(a, uid);
        if(g[a].size() == 2u) {
            que.push(a);
        }
        if(g[b].size() == 2u) {
            que.push(b);
        }
    }

    map<int, int> eidx;
    graph tg(n);
    for(int v = 0; v < n; ++v) {
        for(auto& e : g[v]) {
            if(eidx.count(e.second) == 0) {
                const int id = eidx.size();
                eidx[e.second] = id;
            }
            tg[v].emplace(e.first, eidx[e.second]);
        }
    }
    g = move(tg);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    graph g(n);
    int uid = 0;
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        g[a].emplace(b, uid);
        g[b].emplace(a, uid);
        uid += 1;
    }
    compress_graph(g, uid);

    set<ll> cycles;
    for(int s = 0; s < n; ++s) {
        if(g[s].empty()) continue;
        vector<bool> used_v(n);
        function<void(int, ll)> dfs = [&] (int v, ll used_edge) {
            used_v[v] = true;
            for(auto const& e : g[v]) {
                if(used_edge & (1LL << e.second)) continue;
                used_edge ^= 1LL << e.second;
                if(e.first == s) {
                    cycles.insert(used_edge);
                    used_edge ^= 1LL << e.second;
                    continue;
                }
                if(!used_v[e.first]) {
                    dfs(e.first, used_edge);
                }
                used_edge ^= 1LL << e.second;
            }
            used_v[v] = false;
        };
        dfs(s, 0);
    }

    cout << cycles.size() << endl;
}

感想

こういうのは本番では意外と通しにくい問題という印象がある。