SRM 452 div2 hard: HamiltonPath

問題

TopCoder Statistics - Problem Statement

解法

roads[i][j] == 'Y' だったら頂点 i と頂点 j の間に辺を貼ってみます。

すると, それによっていくつかの連結成分が出来ます。

その連結成分の中に, 次数が 3 以上の頂点 v があると, v に 2 回以上通らないと通りたい辺を通ることが出来ないので答えは 0 です。また, 連結成分内に閉路が出来てしまった場合も答えは 0 になります。

それ以外の場合は, 各連結成分を適当に並べることによって, 目的の HamiltonPath を作ることが出来ます。
連結成分が 2 以上の時は向きが 2 通りあり, 連結成分の個数が p であったとすると それらの並べ方は p! 通りあります。これを掛け算したのが答えです。

const ll MOD = 1e9+7;
bool done[55];
ll fact[55];

class HamiltonPath {
public:
    int countPaths(vector <string> roads) {
        int n = roads.size();
        fact[0] = 1;
        for (int i = 1; i < 55; i++) {
            fact[i] = (fact[i-1]*i)%MOD;
        }
        vector<vi> G(n);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (roads[i][j] == 'Y') {
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        }
        memset(done, false, sizeof(done));
        ll ret = 1;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (done[i]) continue;
            done[i] = true;
            cnt++;
            queue<int> que;
            que.push(i);
            vector<int> vertex;
            while (!que.empty()) {
                int v = que.front(); que.pop();
                vertex.push_back(v);
                for (int u : G[v]) {
                    if (done[u]) continue;
                    done[u] = true;
                    que.push(u);
                }
            }
            int edge = 0;
            for (int v : vertex) {
                if (G[v].size() > 2) return 0;
                edge += G[v].size();
            }
            edge /= 2;
            if (edge >= (int)vertex.size()) return 0;
            if (vertex.size() > 1) ret *= 2;
        }
        ret %= MOD;
        (ret *= fact[cnt]) %= MOD;
        return ret;
    }
};