CodeForces 711D Directed Roads|基环树

基环树入门题

题意：
有 (n) 个点，(n) 条边。每条边由 (i) 指向 (a_i)，求有多少种边的定向方案，使得图中无环。
(2 le n le 2 imes 10^5) ，图中无自环。

思路：
首先，这种 (n) 个点，(n) 条边的联通图，我们称之为基环树。它可以看作一棵树（(n-1) 条边）加上一条边，故有且仅有一个环。在日后的学习中，我们将知道这种图实际就是一个环+环上点类似树的分支，故又称环套树。我们有些时候会先撇开环处理环上的点挂着的子树，再处理环。
在本题中，由于不保证联通，但根据题意可知，每个联通块一定只有与其点数相等的边，我们称其为基环森林

回到本题，要使定向后图中有环，则是环中所有边均为同一方向，共两种情况。其他的边均可以*定向。故设联通块有 (x) 个点，(y) 个点在环上，共有(2 imes 2^{x-y}) 种方案不合法，则每个联通块的答案为
(huge{2^x-2 imes 2^{x-y}}) 。
依照乘法原理，每个联通块乘起来即可。(x) 较大（虽然应该不会使暴力乘超时），我们使用快速幂。找环可以使用DFS.

上代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int cc,to[400200],net[400200],fr[400200],fx[400200],vis[400200];
int q[200200],t,h,g,n,a;long long ans;bool ri[400200];
void addedge(int x,int y)
{
	cc++;to[cc]=y;net[cc]=fr[x];fr[x]=cc;fx[cc]=cc+1;
	cc++;to[cc]=x;net[cc]=fr[y];fr[y]=cc;fx[cc]=cc-1;
}
void dfs(int x)
{
	q[++t]=x;g++;
	for (int i=fr[x];i;i=net[i])
	{
		if (i==fx[vis[x]]) continue;
		if (!vis[to[i]]) 
		{
			vis[to[i]]=i;
			dfs(to[i]);
		}
		else
		{
			if (vis[to[i]]!=i&&vis[to[i]]!=fx[i]&&!ri[to[i]])
			{
				for (int j=t;j;j--) 
				{
					h++;
					ri[q[j]]=true;
					if (q[j]==to[i]) 
					  break;
				}
			}
		}
	}
	t--;
}
long long fst(int x)
{
	long long ans=1,s=2;
	while (x)
	{
		if (x&1)
		{
			ans*=s;
			ans%=mod;
		}
		s*=s;
		s%=mod;
		x>>=1;
	}
	return ans;
}
int main()
{	
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a;
		addedge(i,a);
	}
	ans=1;
	for (int i=1;i<=n;i++)
	{
		if (!vis[i]) 
		{
			vis[i]=cc+1;
			h=0;g=0;
			dfs(i);
			if (h)ans*=(fst(g)-fst(g-h+1)+mod)%mod;else ans*=fst(g);
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

CodeForces 711D Directed Roads|基环树

相关推荐