CodeForces #369 div2 D Directed Roads DFS

题目链接：D Directed Roads

题意：给出n个点和n条边，n条边一定都是从1~n点出发的有向边。这个图被认为是有环的，现在问你有多少个边的set，满足对这个set里的所有边恰好反转一次（方向反转），使得这个图里没有环。

思路：感觉关键是，n个点n条边，且每个点的出度为1，所以图里一定没有复环。想要使图里没环，对于每个连通块(点数为i)里的环（如果有环点数为j），只要不是全翻和全不翻都是满足题意的set，

一共满足题意得set 即为 2^(i-j) * (2^j-2)。所有的连通块方案相乘即为最后的方案数ans.

找到所有的连通块并且得到里面的环的点数：邻接表存图dfs遍历连通块，全局变量标记当前连通块的点数，设置num数组标记每个点被访问时的次序，当再次被访问到时，两次标号相减

即为环的点数。但是这样的样例：

2 1 1 1

搜出来的环数会是1，因为3和4搜到1的时候确实1已经被标记了。而且覆盖了前面的2。然后... ... 本来想着先过样例吧...就在所有找到的环数里取max，觉得一定不对，比如这样：

2 1 1 1 1 1 1 1 1 1

居然是对的。

然后最后的ans被莫名其妙的%mod爆int。

附AC代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#define maxn 2000100
#define LL long long
using namespace std;
const LL mod = 1e9+7;

struct Node {
    int u, v;
    int nxt;
}edge[maxn]; //边数

int tot;
LL ans;
int num[maxn];
int numCir;
LL pow2[maxn];
int cntt;
int head[maxn];
bool vis[maxn];

void init() {
    memset(num, 0, sizeof(num));
    ans = 1;
    tot = 0;
    numCir = 0;
    memset(head, -1, sizeof(head));
    pow2[0] = 1;
    for (int i=1; i<=maxn; ++i) {
        pow2[i] = (pow2[i-1]*2)%mod;
    }
   // memset(vis, 0, sizeof(vis));
}

void addEdge(int u, int v) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}

void dfs(int id, int cnt) {
    cntt++;
    //cout << id << "@+++++" << cntt << endl;
    for (int i=head[id]; i!=-1; i=edge[i].nxt) {
        int v = edge[i].v;
        if (!vis[v]) {
            num[v] = cnt+1;
            vis[v] = 1;
            dfs(v, cnt+1);
        }
        else { ///找到环了
            numCir = max(cnt + 1 - num[v], numCir);
        }
    }
    ///搜完了整个连通块
}

int main() {
    //freopen("in.cpp", "r", stdin);
    int n;
    while(~scanf("%d", &n)) {
        init();
        // build map
        for (int i=1; i<=n; ++i) {
            int temp;
            scanf("%d", &temp);
            addEdge(i, temp);
            addEdge(temp, i);
        }
        memset(vis, 0, sizeof(vis));

        for (int i=1; i<=n; ++i) {
            //cout << i << "@
";
            if (vis[i]) continue;
            vis[i] = 1;
            num[i] = 1;
            cntt = 0;
            numCir = 0;
            dfs(i, 1);
           // cout << numCir << " " << cntt << endl;
            if (numCir == 0) ans += pow2[cntt];
            else ans = (ans * ((pow2[cntt-numCir]*(pow2[numCir]-2))%mod))%mod;
        }
        ans %= mod;
        printf("%I64d
", ans);
    }
    return 0;
}