解析在代码后面

代码

#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