Description：

一个每个点都有一条出边的图，反转任意条边使得图中不存在环，求方案数。

$1\le N\le 2\times10^5$

Solution：

图是一个基环树森林，树枝上的边可以随便反转，环上的边只要不同向即可，设环长为 $len$ ，联通块大小为 $siz$ ，则 $ans=\sum(2^{len}-2)\times 2^{siz}$ ，用 $tarjan$ 求出所有的强连通分量大小不为一的就是环。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

#define MOD 1000000007

typedef long long ll;

ll ans = 1;

ll power(ll a,int b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

bool v[MAXN];

int siz[MAXN],scc = 0;

stack<int> s;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(dfn[k] == low[k])

	{

		int t;

		++scc;

		do

		{

			t = s.top();s.pop();

			v[t] = false;

			++siz[scc];

		}while(t != k);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a;

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

	{

		scanf("%d",&a);

		add(i,a);

	}

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

	{

		if(dfn[i] == 0)

		{

			tarjan(i);

		}

	}

	for(int i = 1;i <= scc;++i)

	{

		if(siz[i] == 1)

		{

			ans = ans * 2 % MOD;

		}

		else

		{

			ans = ans * (power(2,siz[i]) - 2) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}