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+5;
const int mod = 1e9+7; 
int n,tot,col;
ll ans,cnt,dfn[N];
int nxt[N],vis[N];

ll pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }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]+1;      
        ans = ans*(pow((ll)2,num)-2)%mod;
        cnt-=num;     //cnt表示链上节点的数量      
    }
}
int main(){
    scanf("%d",&n);
    REP(i,1,n)scanf("%d",&nxt[i]);
    ans=1;cnt=n; 
    REP(i,1,n) if(!vis[i]) {
        tot=0;++col;
        dfs(i);
    }
    ans = ans*(pow((ll)2,cnt))%mod;
    printf("%lld
",ans);
}