裏紙

ほぼ競プロ、たまに日記

CF 711 D - Directed Roads

問題

Problem - D - Codeforces

問題概要

1番からn番まで番号が振られたn個の街がある。この街の間にはn本の有向辺があり、それらはi番の街からa_i番の街へ伸びている( 1 \le i \le n , i \neq a_i)(つまりそれぞれの街から1本ずつ有向辺が出ており、自己ループはない状態))。

今、自由に何本でもこの辺の向きを変えることが出来る。そのときに1つでも大きさ2以上の閉路ができている状態のことをconfusingと呼ぶことにする。自由に辺の向きを変えることができるので、グラフの形としては2^n通りの形が考えられるが、このうちconfusingでないものは何通りあるか、 10^9 + 7で割った余りを答えよ。向きを変えた結果多重辺ができてしまうものや、ある街にたどり着くことができなくなっても構わないものとする。

  •  2 \le n \le 200000
  •  i \neq a_i (1 \le i \le n)

イデア

まず、このグラフを無向グラフとして考えると、いくつかの連結成分に分かれていて、例えばある連結成分に繋がっている街の数が合計でXだった時、その連結成分内に辺がX本存在していることになる。つまり、1つの連結成分に対して、X-1本だと木ができるので、そこに1本足していると考えてちょうど1つだけ閉路が存在することになる。

そしてその閉路の大きさがYであるとすると、回る向きを考えて閉路が完成する有向辺の組み合わせは2通りとなる。そして、残りの閉路に関与していない連結成分の辺の向きはどっちであろうと関係がないので、この連結成分に関してconfusingではない有向辺の構成方法は (2^Y - 2) * 2^{X-Y}通りである。後はこれを連結成分ごとにたってその積を取れば良い。

ここまで考察できてればあとはやるだけでしょと思ってたのだが、閉路検出などをどうすればよいか頭がこんがらがってイマイチわからずコンテストが終了してしまったが、dfsで簡単にできるらしい...余り書いたことが無かった気がするので、これは本当に反省。

というかわざわざ無向グラフに落としていることがこの問題を難しくしていた。このように各頂点から1本ずつ有向辺が出ているようなグラフの形、何かで見たこと有る気がすると思ったらGCJのやつでみた(http://imulan.hatenablog.jp/entry/2016/06/04/015235)と思って、このようなグラフには"Functional Graph"とかの呼び名があって(参考:https://en.wikipedia.org/wiki/Pseudoforest#Graphs_of_functions)、連結成分のどの位置からスタートしても最終的に閉路にたどり着く。

つまり、このはじめの有向辺の状態の時点で、それぞれの連結成分は「閉路を構成する辺」と「その閉路に向かって近づいていく辺」だけで構成されていることになる。なんか一瞬納得が行かないような気もするが、ある頂点からスタートして、有向辺を1つだけ伸ばして頂点へ移動するとなった時に、この問題では自己ループがないのであり得ないが自分へ有向辺を伸ばしたら閉路になっているし、他の頂点へ伸ばしていって、どんなに伸ばしていってもn-1本引いた時点で木が構成され、そこからどの頂点に伸ばしても結局閉路が出来る。となるとイメージしやすい。こうなれば簡単なdfsでできるという公式の解説にも納得した。前に似たような問題やってのにできなかったのか...

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const ll mod=1e9+7;
const int N=200000;

int a[N];

int vis[N];
vector<int> cycles;
int c_idx=0;

//閉路検出
void dfs2(int x)
{
    ++cycles[c_idx];
    vis[x]=3;
    if(vis[a[x]]==3) return;
    dfs2(a[x]);
}

void dfs(int x)
{
    //まず頂点に入ったら暫定
    vis[x]=2;

    if(vis[a[x]]==0)
    {
        //次の頂点へ
        dfs(a[x]);
    }
    else if(vis[a[x]]==1)
    {
        //その先がもう処理終了している位置なのでここで打ち切り
        vis[x]=1;
        return;
    }
    else
    {
        //閉路検出
        cycles.pb(0);
        dfs2(x);
        ++c_idx;
    }

    //処理終了
    vis[x]=1;
}

int main()
{
    //2の累乗を計算しておく
    ll pw[N+1];
    pw[0]=1;
    for(int i=1; i<=N; ++i) pw[i]=(pw[i-1]*2)%mod;

    int n;
    scanf(" %d", &n);
    rep(i,n)
    {
        scanf(" %d", &a[i]);
        --a[i];
    }

    //visのフラグについて
    //0:まだ,1:完了,2:暫定到達,3:閉路検出
    memset(vis,0,sizeof(vis));
    rep(i,n)
    {
        if(vis[i]==0) dfs(i);
    }

    ll ans=1;

    int not_cycle=n;
    rep(i,c_idx)
    {
        (ans*=(pw[cycles[i]]-2+mod)%mod)%=mod;
        not_cycle-=cycles[i];
    }
    (ans*=pw[not_cycle])%=mod;

    cout << ans << endl;
    return 0;
}