CodeForces 711D Directed Roads (DFS找环+组合数)

<题目链接>

题目大意：

给定一个$n$条边，$n$个点的图，每个点只有一条出边(初始状态)，现在能够任意对图上的边进行翻转，问你能够使得该有向图不出先环的方案数有多少种。

解题分析：

很明显本题需要对环的部分和链的部分分开进行讨论，对于环的部分，能够使得该环不为有向环的方案数有$2^k-2$种($k$为环上的点数，相当于减去环上所有边都是顺时针和逆时针情况)，对于链的部分，方案数就是$2^k$($k$为链上的点数)。因为初始状态每个点只有一条出边，所以即使存在环，也一定是简单环(即不存在环套环的情况)，找环直接用DFS即可。

#include <bits/stdc++.h>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

typedef long long ll;

const int N = 2e5+;

const int mod = 1e9+;

int n,tot,col;

ll ans,cnt,dfn[N];

int nxt[N],vis[N];

ll pow(ll a,ll b){

    ll res=;

    while(b){

        if(b&)res=(res*a)%mod;

        a=(a*a)%mod;

        b/=;

    }return res%mod;

}

void dfs(int u){

    vis[u]=col;

    dfn[u]=++tot;

    int v=nxt[u];

    if(!vis[v])dfs(v);

    else if(vis[v]==col){       //如果遇到相同标记的点，表示遇到了环

        ll num = dfn[u]-dfn[v]+;

        ans = ans*(pow((ll),num)-)%mod;

        cnt-=num;     //cnt表示链上节点的数量

    }

}

int main(){

    scanf("%d",&n);

    REP(i,,n)scanf("%d",&nxt[i]);

    ans=;cnt=n;

    REP(i,,n) if(!vis[i]) {

        tot=;++col;

        dfs(i);

    }

    ans = ans*(pow((ll),cnt))%mod;

    printf("%lld\n",ans);

}