codeforces 711D Directed Roads

题目链接:cf 711D


这个题主要是读题意比较难

因为是n个点,n条边,那么肯定会有环存在

那么,一旦出现了环,就出现了题中给的非法情况


那么,我们根据连通情况将图中的点分类(按照乘法原理,先各自计算当前的集合之中有几个数,然后相乘)

在每个集合中,如果出现了环,假设环中的点数为x,那么可以的方案数目为(2^x-2)(样例1)

如果既有环,又有链子,假设环中的点数为x,链子中的点数为y,那么可以的方案数目为(2^x-2)*(2^y),当然在操作中是只能求出x+y的(样例3)


那么,这个题就是dfs搜索搞定的

cf的题目很多都是需要数学方法先想明白,其实代码实现确实不难吧


#include<bits/stdc++.h>
using namespace std;

#define LL __int64
const int maxn=2e5+50;
struct Edge{
    int nxt,to;
}edge[maxn<<1];
LL mod=1e9+7,d[maxn],ans,sum,f[maxn];
int Head[maxn],cnt;
bool vis[maxn];

void addedge(int u,int v){
    edge[cnt].nxt=Head[u];
    edge[cnt].to=v;
    Head[u]=cnt++;
}

void dfs(int u,int p,int dep){
    if (!ans&&vis[u]){
        ans=dep-d[u]?dep-d[u]:2;
        return;
    }
    else if (vis[u]) return;
    d[u]=dep;
    vis[u]=true;
    ++sum;
    for(int i=Head[u];~i;i=edge[i].nxt){
        int v=edge[i].to;
        if (v==p) continue;
        dfs(v,u,dep+1);
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    f[0]=1;
    for(int i=1;i<maxn;i++) f[i]=f[i-1]*2LL%mod;
    int n,u;
    while(scanf("%d",&n)!=EOF){
        memset(Head,-1,sizeof(Head));
        memset(vis,0,sizeof(vis));
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&u);
            addedge(u,i);
            addedge(i,u);
        }
        LL res=1;
        for(int i=1;i<=n;i++)
        if (!vis[i]){
            ans=sum=0;
            dfs(i,-1,1);
            res=((res*(f[ans]-2)%mod+mod)*f[sum-ans])%mod;
        }
        cout<<res<<endl;
    }
    return 0;
}


全部评论

相关推荐

12-09 12:21
门头沟学院 C++
l11hy:今早刚开,已满足
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务