Codeforces 711 D. Directed Roads (DFS判环)

题目链接：http://codeforces.com/problemset/problem/711/D

给你一个n个节点n条边的有向图,可以把一条边反向,现在问有多少种方式可以使这个图没有环。

每个连通量必然有一个环，dfs的时候算出连通量中点的个数y，算出连通量的环中点的个数x，所以这个连通量不成环的答案是2^(y - x) * (2^x - 2)。

最后每个连通量的答案相乘即可。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef __int64 LL;

 typedef pair <int, int> P;

 const int N = 2e5 + ;

 struct Edge {

     int next, to;

 }edge[N << ];

 LL mod = 1e9 + , d[N], ans, f[N], sum;

 int head[N], cnt;

 bool vis[N];

 LL fpow(LL a, LL b) {

     LL res = ;

     while(b) {

         if(b & )

             res = res * a % mod;

         a = a * a % mod;

         b >>= ;

     }

     return res;

 }

 inline void add(int u, int v) {

     edge[cnt].next = head[u];

     edge[cnt].to = v;

     head[u] = cnt++;

 }

 void dfs(int u, int p, int dep) {

     if(!ans && vis[u]) {

         ans = dep - d[u] ? dep - d[u] : ;

         return ;

     } else if(vis[u]) {

         return ;

     }

     d[u] = dep;

     vis[u] = true;

     ++sum;

     for(int i = head[u]; ~i; i = edge[i].next) {

         int v = edge[i].to;

         if(v == p)

             continue;

         dfs(v, u, dep + );

     }

 }

 int main()

 {

     f[] = ;

     for(int i = ; i < N; ++i) {

         f[i] = f[i - ]*2LL % mod; //2的阶乘预处理

     }

     memset(head, -, sizeof(head));

     cnt = ;

     int n, u;

     scanf("%d", &n);

     for(int i = ; i <= n; ++i) {

         scanf("%d", &u);

         add(u, i);

         add(i, u);

     }

     LL res = ;

     for(int i = ; i <= n; ++i) {

         if(!vis[i]) {

             ans = sum = ;

             dfs(i, -, );

             res = ((res * (f[ans] - ) % mod + mod) % mod * f[sum - ans]) % mod;

         }

     }

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

     return ;

 }