此文章可以使用目录功能哟↑(点击上方[+])
比赛链接→Codeforces Round #369 (Div. 2)
Codeforces Problem 711D Directed Roads
Accept: 0 Submit: 0
Time Limit: 2 seconds Memory Limit : 256 megabytes
Problem Description
ZS the Coder and Chris the Baboon has explored Udayland for quite some time. They realize that it consists of n towns numbered from 1 to n.
There are n directed roads in the Udayland. i-th of them goes from town i to some other town ai (ai?≠?i). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town A to town B before the flip, it will go from town B to town A after.
ZS the Coder considers the roads in the Udayland confusing, if there is a sequence of distinct towns A1,?A2,?...,?Ak (k?>?1) such that for every 1?≤?i?<?k there is a road from town Ai to town 
Now ZS the Coder wonders how many sets of roads (there are 
Note that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.
Input
The first line of the input contains single integer n (2?≤?n?≤?2·10^5) — the number of towns in Udayland.
The next line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?n,?ai?≠?i), ai denotes a road going from town i to town ai.
Output
Print a single integer — the number of ways to flip some set of the roads so that the resulting whole set of all roads is not confusing. Since this number may be too large, print the answer modulo 10^9?+?7.
Sample Input
2 3 1
4
2 1 1 1
5
2 4 2 5 3
Sample Output
8
28
Hint
Consider the first sample case. There are 3 towns and 3 roads. The towns are numbered from 1 to 3 and the roads are 
The sets of roads that ZS the Coder can flip (to make them not confusing) are {1},?{2},?{3},?{1,?2},?{1,?3},?{2,?3}. Note that the empty set is invalid because if no roads are flipped, then towns 1,?2,?3 is form a directed cycle, so it is confusing. Similarly, flipping all roads is confusing too. Thus, there are a total of 6 possible sets ZS the Coder can flip.
The sample image shows all possible ways of orienting the roads from the first sample such that the network is not confusing.
Problem Idea
解题思路:
【题意】
n个城镇,n条单向路
城镇i有一条通往城镇ai的单向路
现在可以改变一些单向路方向,即原本是城镇Ai->Aj,改变方向后变为Aj->Ai
问有多少种改变方案,使得改变某些单向路方向之后,图不存在环路
【类型】
Tarjan算法
【分析】
解决此题的核心其实是找到图中的规律
即如何改变道路方向,才能使得原本有环路的图变成无环路的图
例如下图
很显然,想要破坏原本的环路,我们只需将其中一条路反向就行了
当然这只是其中一种解法,我们当然还可以将其中两条路、三条路……反向
这样都可以破坏原本的环路,但惟独不能将环路内的所有单向路反向
毕竟,这样做的效果只是将原本的环路整体反向,环路依旧存在,只是变成了下面这样的效果
所以,由上述例子可以得出,对于由k个点构成的环路部分,要想破坏原本的环路,共有
那对于有分支的图呢?破坏原本环路的方案又有多少种?
明显地,有分支的图也必定包含环路,环路在处理上与上述提到的没有什么区别,而分支部分(上图虚线部分),仔细考虑一下也会发现,这部分是可以任意改变路的方向的,即改不改都不会影响环路本身
所以题目就转化成了,假设图上有k个环路,对于第i个环路,有ai个结点,此时,消除环路的总体方案数为
那接下来的任务就是求环路个数及每个环路内的结点数
解法有很多种,本人采用的是Tarjan算法
因为在有向图中,一个环路部分就相当于一个强连通分量,而求解强连通分量,Tarjan算法是必然会想到的
然后,剩下的就是套个Tarjan算法模板搞定此题
【时间复杂度&&优化】
O(n)
题目链接→Codeforces Problem 711D Directed Roads
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 200005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
struct edge
{int to,next;
}e[N];
int p,k,h[N],dfn[N],low[N],belong[N],ans,c[N];
bool instack[N],vis[N];
__int64 f[N];
stack<int> s;
void add_edge(int u,int v)
{e[p].to=v;e[p].next=h[u];h[u]=p++;
}
void Clear()
{ans=k=p=0;memset(h,-1,sizeof(h));memset(instack,false,sizeof(instack));memset(dfn,0,sizeof(dfn));memset(vis,false,sizeof(vis));memset(c,0,sizeof(c));
}
void Tarjan(int u)//Tarjan算法求有向图的强连通分量,时间复杂度O(n+m)
{int i,v,Top;dfn[u]=low[u]=k++;s.push(u);//入栈vis[u]=true;instack[u]=true;//标记在栈中for(i=h[u];i+1;i=e[i].next){//枚举v的每一条边v=e[i].to;//v所邻接的边if(!dfn[v]){//未被访问Tarjan(v);//继续向下找low[u]=min(low[u],low[v]);//更新结点v所能到达的最小次数层}else if(instack[v])low[u]=min(dfn[v],low[u]);}if(low[u]==dfn[u]){ans++;while(!s.empty()){Top=s.top();s.pop();belong[Top]=ans;//出栈结点t属于cnt标号的强连通分量instack[Top]=false;//标记不在栈中if(Top==u)break;}}
}
int main()
{int n,i,x,k=0;__int64 res=1;Clear();scanf("%d",&n);f[0]=1;for(i=1;i<=n;i++)f[i]=f[i-1]*2%mod;for(i=1;i<=n;i++){scanf("%d",&x);add_edge(i,x);}for(i=1;i<=n;i++)if(!vis[i])Tarjan(i);for(i=1;i<=n;i++)c[belong[i]]++;for(i=1;i<=ans;i++)if(c[i]>1)res=res*(f[c[i]]-2+mod)%mod;//环路部分else if(c[i]==1)k++;//记录分支部分的结点个数res=res*f[k]%mod;printf("%I64d\n",res);return 0;
}