codeforces 711 D.Directed Roads（tarjan 强连通分量 ）

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

题目大意：Udayland有一些小镇，小镇和小镇之间连接着路，在某些区域内，如果从小镇Ai开始，找到一个环，环中每个小镇只经过一次，最终回到了Ai，那么认为这个环是混乱的，现在需要治理这种混乱。可以做的操作是改变环上某个小镇Ak到小镇Aj路的方向，使得无法从Ai开始绕这个环再次回到Ai，那么可以认为混乱被治理，问需有多少种改变路径方向的方案可以使得整个Udayland不混乱？求出方案数。

题解思路：涉及到环，首先要求出强联通分量个数，建图套一下tarjan的模板。对于每个强连通分量，在此题意的限制条件下，其边的数量为每个强连通分量的点的数量，那么从tarjan中可以轻易得到边的数量，每条边的方向可以是正反两种，由于可以改变边的方向，那么整个强连通分量的边可以变为2的n次方种（n是某个强连通分量中点的个数），若是形成环路（即强连通分量），只能是正序A1 ->A2 ->A3 ....Ak-1 -> Ak->A1或者是逆序A1->Ak -> Ak-1->....A2->A1两种情况，这两种被认为是混乱的，所以可以改变成不混乱的情况有pow(2,n) - 2种，那么最终的答案就是所有强连通分量不混乱的情况的方案数相乘了，求解过程中根据题意求余即可。

AC代码:

#include<iostream>

#include<vector>

#include<cmath>

#include<stack>

#include<algorithm>

using namespace std;

struct node{

	vector<int> vex;

};

node g[200008];

int dfn[200008];

int low[200008];

int visit[200008];

stack<int> stk;

int ans = 0;

int tot;

int cnt;

vector<int> sum;

void tarjan(int x){

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

	visit[x] = 1;

	stk.push(x);

	for(int i = 0;i<g[x].vex.size();i++){

		if(!dfn[g[x].vex[i]]){

			tarjan(g[x].vex[i]);

			low[x] = min(low[x],low[g[x].vex[i]]);

		}

		else if(visit[g[x].vex[i]]){

			low[x] = min(low[x],dfn[g[x].vex[i]]);

		}

	}

	if(low[x] == dfn[x]){

		int temp = 0;//记录每个连通分量的节点个数

		ans++;

		while(x!=stk.top()){

			temp++;

			visit[stk.top()] = 0;

			stk.pop();

		}

		temp++;

		visit[stk.top()] = 0;

		stk.pop();

		if(temp>1)

		   cnt+=temp;

		sum.push_back(temp); //记录每个连通分量的节点个数

	}

}

int main(){

	int N;

	cin>>N;

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

		int Ai;

		cin>>Ai;

		g[i].vex.push_back(Ai);

	}

	for(int i = 1;i<=N;i++){//套tarjan模板求强连通分量

		if(!dfn[i])

		   tarjan(i);

	}

	long long int fac[200008];

	int mod = 1000000007;

	fac[0] = 1;

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

		fac[i] = (fac[i-1]*2)%mod;//打表 2的n次方和mod求余

	}

	long long int res = fac[N-cnt]%mod;

	for(int i = 0;i<ans;i++){

		if(sum[i]>1)

	       res = res * (fac[sum[i]]-2+mod)%mod;

	}

	cout<<res%mod;

	return 0;

}