解析在代码后面 代码 #include #define N 100001 using namespace std; typedef long long LL; int to[N],d[N],q[N],sum; const int mod=1e9+7; LL pow(LL a,int b) {     LL res=1;     for(;b;b>>=1,a=a*a%mod)         if(b&1) res=res*a%mod;     return res; } void dfs(int x) {     sum++;     d[x]=0;     if(d[to[x]]) dfs(to[x]); } int main() {     freopen("road.in","r",stdin);     freopen("road.out","w",stdout);     int n;     scanf("%d",&n);     for(int i=1;i<=n;i++) scanf("%d",&to[i]),d[to[i]]++;     int h=1,t=0;     for(int i=1;i<=n;i++)         if(!d[i]) q[++t]=i;     while(h<=t)     {         if(!(--d[to[q[h]]])) q[++t]=to[q[h]];         ++h;     }     LL ans=pow(2,t);      for(int i=1;i<=n;i++)         if(d[i])         {             sum=0;             dfs(i);             ans=ans*(pow(2,sum)-2)%mod;         }     printf("%I64d",ans); } 设图中有m个环，每个环有si条边，有k条边不在环中 ans= （2^s1 -2）*（ 2^s2 -2）* （2^s3 -2）…… *（ 2^sm -2）* 2^k （环上的边只有两种可能形成环） 找环好找，怎么找树？ 一种方法是tarjan找出所有的环，总边数-环的边数=树的边数 std用了拓扑排序

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com