D. Directed Roads
题意
给出n个点n条边的有向图(n<1e5)
求出有多少种边集 使得反转集合种边的方向后 图中无环
题解
上图举例了一个n个点n条边的有向图
容易发现要通过反转某些边获得无环图 需要从每一个环中取出至少一个边反转
所以选择的边集中必须包含各个环中的至少一条边
对于一个环i 需要反转的边集有$C_{loopsize[i]}^1+C_{loopsize[i]}^2+…..C_{loopsize[i]}^{loopsize[i]-1}$ 种
已知$∑_{i=0}^nC_n^i=2^n$ 所以对于一个环i需要反转的边集有$2^{loopsize[i]}-2$种
通过组合数学的知识对于m个环则有
$(2^{loopsize[1]}-2) (2^{loopsize[2]}-2)…. (2^{loopsize[m]}-2)$ 种边集
对于非环中的边 无论它如何改变方向都不会产生新的环所以 被选中要反转的边中
可以有0条,1条…. $n-∑loopsize[i]$ 条非环边
所以答案的方案数为$(2^{loopsize[1]}-2) (2^{loopsize[2]}-2)…. (2^{loopsize[m]}-2) (2^{n-∑loopsize[i]})$
对于非环边 我们可以通过拓扑排序中删去入度为0的边 的过程来统计
而对于每个环的大小
在这个题目中不会有环套环的情况因为n个点n条边每个点一个出边只会出现简单环
所以用简单dfs统计每个环的大小即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
vector<int>mp[Max];
int in[Max],out[Max],sz[Max];
bool vis[Max];
int Topu(int n){
queue<int>q;
int cnt=0;
for(int i=1;i<=n;i++)if(!in[i])q.push(i),cnt++,vis[i]=1;
while(!q.empty()){
int pos=q.front();q.pop();
for(auto i:mp[pos]){
in[i]--;
if(!in[i]){
cnt++;vis[i]=1;
q.push(i);
}
}
}
return cnt;
}
void dfs(int now){
sz[now]=1;vis[now]=1;
for(auto i:mp[now]){
if(vis[i])continue;
dfs(i);
sz[now]+=sz[i];
}
}
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=(ans*x)%mod;
x=(x*x)%mod;y>>=1;
}
return ans;
}
int main() {
int n;cin>>n;
for(int i=1;i<=n;i++){
int v;cin>>v;
mp[i].push_back(v);
in[v]++;
out[i]++;
}
int outloop=Topu(n);
ll ans=qpow(2,outloop);
for(int i=1;i<=n;i++){
if(vis[i])continue;
dfs(i);
ans=(ans*(qpow(2,sz[i])-2+mod)%mod)%mod;
}
cout<<ans<<endl;
}
|