Codeforces Round #369 (Div. 2) Directed Roads

問題

codeforces.com

n 個の頂点からなるグラフが与えられる。各頂点 i から, A[i] への有向グラフが一本ずつ生えている。

このグラフの辺の向きをいくつか入れ替えることにより, このグラフにサイクルができないようにしたい(つまり x0 -> x1 -> ... -> xm -> x0 みたいな辺の向きができないようにしたい)。このような辺の向きの場合の数はいくつあるか。

解法

n 頂点, n 辺なので, グラフが連結ならこの中に閉路は一つだけあります。この閉路のなかで辺の向きがすべて同じ(このようなものは 2 通りある)時上記のサイクルができてしまうので, サイクルを構成する頂点数が cnt であるとして, 2^n - 2*2^(n-cnt) 通りが答えになります。

グラフが連結でない場合は これらを掛け算すれば良いです。

const int MAXN = 200200;
const int MOD = 1e9+7;
int A[MAXN];

vi G[MAXN];
int degree[MAXN];
bool done[MAXN];

void dfs(int v, int& num, int& cnt) {
    done[v] = true;
    num++;
    if (degree[v]) cnt++;
    for (int ch : G[v]) {
        if (!done[ch]) dfs(ch, num, cnt);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        A[i]--;
        G[i].push_back(A[i]);
        G[A[i]].push_back(i);
    }
    queue<int> que;
    for (int i = 0; i < n; i++) {
        degree[i] = G[i].size();
        if (degree[i] == 1) {
            que.push(i);
            degree[i] = 0;
        }
    }
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        for (int v : G[now]) {
            if (degree[v] == 0) continue;
            if (--degree[v] == 1) {
                degree[v] = 0;
                que.push(v);
            }
        }
    }
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        if (!done[i]) {
            int num = 0, cnt = 0;
            dfs(i, num, cnt);
            //cout << i << " " << num << " " << cnt << endl;
            ll tmp = 1;
            for (int j = 0; j < num; j++) {
                tmp = (2*tmp)%MOD;
            }
            ll minus = 1;
            for (int j = 0; j < num-cnt+1; j++) {
                minus = (2*minus)%MOD;
            }
            tmp = (tmp-minus+MOD)%MOD;
            (ans *= tmp) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}