codeforces Round#369 div2

codeforces Round#369 div2"/>

codeforces Round#369 div2

题意：n个点n条有向边（无自环），求边的集合的方案数，使得翻转这些边的方向后无环。

题解：题目给出的图不会环套环（环套环的话，至少有一个点要有两个出度，但题目是每个点一个出度），所有直接求强连通分量，贡献分两种情况：

1.形成环的强连通：2^n-2（本身和所有边反向不合法，其余都合法）;

2.单点的强连通：2（该点的出边对合法性无影响）；

累乘即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>using namespace std;typedef long long LL;
const int M=1000000007;
const int N=400000+10;vector<int>V[N];
int n;
int Time,dfn[N],low[N],sta[N],instack[N],g[N];
int belong[N],h,Col;
LL RP(LL a,LL b)
{LL Ans=1;for (;b;b>>=1){if (b&1)Ans=Ans*a%M;a=a*a%M;}return Ans;
}
void tarjan(int u)
{Time++;dfn[u]=low[u]=Time;sta[++h]=u;instack[u]=1;for (int i=0;i<V[u].size();i++){int v=V[u][i];if (!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if (instack[v]==1)low[u]=min(low[u],low[v]);}if (dfn[u]==low[u]){Col++;while (sta[h]!=u){instack[sta[h]]=-1;belong[sta[h]]=Col;h--;g[Col]++;}instack[sta[h]]=-1;belong[sta[h]]=Col;h--;g[Col]++;}
}
int main()
{//freopen("1.txt","r",stdin);scanf("%d",&n);for (int i=1;i<=n;i++){int a;scanf("%d",&a);V[i].push_back(a);}memset(g,0,sizeof g);memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);memset(instack,0,sizeof instack);h=Time=Col=0;for (int i=1;i<=n;i++)if (!dfn[i])tarjan(i);LL Ans=1;for (int i=1;i<=Col;i++)if (g[i]>1){Ans=Ans*(RP(2,g[i])-2+M)%M;}else Ans=Ans*2%M;cout<<Ans<<endl;return 0;
}