Directed Roads

Directed Roads

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

dfs

刚开始的时候想歪了，以为同一个连通区域会有多个环，实际上每个点的出度为1，也就是说每个连通区域最多就只有一个环。

那么每一个连通区域的方法数就 = （2^环内边数-2）*（2^环外边数） [因为环内有两种情况形成圈，不可取]，

总方法数 = 不同连通区域的方法数的乘积；

于是我把整个有向图先存储成无向图，用dfs判断该连通区域有没有环，再cls掉环外的边，之后再继续dfs...

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<iostream>
 5 #define N 200005
 6 #define M (int)(1e9+7)
 7 #define special 9
 8 using namespace std;
 9 typedef long long LL;
10 struct nod{
11     LL edge;
12     LL to;
13     nod(LL a,LL b){
14         edge=a;
15         to=b;
16     }
17 };
18 vector<nod>node[N];
19 LL n;
20 LL vis[N];
21 LL dfs(LL index,LL num){
22     for(LL i=0;i<node[index].size();++i){
23         LL e=node[index][i].edge,to=node[index][i].to;
24         if(vis[e]==-1){
25             vis[index]=to;
26             LL temp=dfs(e,num+1);
27             if(temp)return temp;
28             vis[index]=-1;
29         }else if(vis[e]==to){
30             vis[index]=to;
31             vis[e]=special;
32             return num;
33         }
34     }
35     return 0;
36 }
37 LL cls(LL index,LL num){
38     for(LL i=0;i<node[index].size();++i){
39         vis[index]=-1;
40         LL e=node[index][i].edge;
41         if(vis[e]==special)return num;
42         if(vis[e]!=-1)
43             return cls(e,num+1);
44     }
45     return 0;
46 }
47 LL pow(LL a,LL b){
48     LL base=a,temp=1;
49     while(b){
50         if(b&1)temp=(temp*base)%M;
51         base=(base*base)%M;
52         b>>=1;
53     }
54     return temp;
55 }
56 LL mod(LL a,LL b){
57     LL base=a,temp=0;
58     while(b){
59         if(b&1)temp=(temp+base)%M;
60         base=(base+base)%M;
61         b>>=1;
62     }
63     return temp;
64 }
65 int main(void){
66     memset(vis,-1,sizeof(vis));
67     LL res=0;
68     scanf("%I64d",&n);
69     for(LL i=1;i<=n;++i){
70         LL vertice;
71         //cin>>vertice;
72         scanf("%I64d",&vertice);
73         node[i].push_back(nod(vertice,1));
74         node[vertice].push_back(nod(i,0));
75     }
76     for(LL i=1;i<=n;++i){
77         if(vis[i]==-1){
78             LL cyc_temp=dfs(i,1);
79             if(vis[i]!=special&&vis[i]!=-1){
80                 LL un_temp=cls(i,1);
81                 cyc_temp-=un_temp;
82             }
83             if(res==0&&cyc_temp)res=pow(2,cyc_temp)-2;
84             else if(cyc_temp)res=mod(res,(pow(2,cyc_temp)-2));
85         }
86     }
87     LL un_sum=0;
88     for(LL i=1;i<=n;++i)
89         if(vis[i]==-1)un_sum++;
90     if(res)res=mod(res,pow(2,un_sum));
91     else res=pow(2,un_sum);
92     //cout<<res<<endl;
93     printf("%I64d
",res);
94 }

View Code

然而这样会T（想象一种坏的情况：只有一个连通区域，且环在末尾，这样差不多是O（n^2）的复杂度）

仔细想过后，其实不需要将有向图转化为无向图，因为每个点的出度为1，如果有环，那么有向图也必然成环，改进后复杂度就成了O（n）

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define N 200005
 5 #define M (int)(1e9+7)
 6 using namespace std;
 7 typedef long long LL;
 8 LL n,sum=1;
 9 LL a[N];
10 LL vis[N];
11 LL pow(LL a,LL b){
12     LL base=a,temp=1;
13     while(b){
14         if(b&1)temp=(temp*base)%M;
15         base=(base*base)%M;
16         b>>=1;
17     }
18     return temp;
19 }
20 int main(void){
21     cin>>n;
22     LL res=n;
23     for(LL i=1;i<=n;++i)cin>>a[i];
24     for(LL i=1;i<=n;++i){
25         if(!vis[i]){
26             LL index=i;
27             while(1){
28                 vis[index]=i;
29                 index=a[index];
30                 if(vis[index])break;
31             }
32             if(vis[index]!=i)continue;
33             LL node=0,temp=index;
34             while(1){
35                 node++;
36                 temp=a[temp];
37                 if(temp==index)break;
38             }
39             res-=node;
40             sum=(sum*(pow(2,node)-2))%M;
41         }
42     }
43     sum=(sum*pow(2,res))%M;
44     cout<<sum<<endl;
45 }