GOATzhao00 2019-12-08 23:40
浏览 176

CCPC2019-秦皇岛F HDU-6736为什么这个题目把前向星换成邻接表就能AC啊?

在用前向星存图并遍历的时候,会WA
而对于邻接表存的图,就不会WA,可以AC,为什么?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 3e5+100;
const int maxm = 5e5+100;
int n, m;
struct node{
    int to, next;
    node(){ }
    node(int a, int b):to(a), next(b){  }
};
node edge[maxm];
int head[maxn];
int cnt;
ll num;
ll ans;
ll vis[maxn];
void init(){
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    cnt = 0;
    num=0;
}
ll quick_pow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1)res=(res*a%mod)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void addedge(int u, int v){
    edge[cnt] = node(v, head[u]);
    head[u]=cnt++;
}
void dfs(int u, int fa){
    vis[u]=vis[fa]+1;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        if(!vis[v])dfs(v, u);
        else if(vis[u]>vis[v]){
            ll tmp = vis[u]-vis[v]+1;
            num += tmp; //对于环内的边 2^k - 1,因为不能全删 
            ans = (ans%mod*(quick_pow(2, tmp)-1)%mod)%mod;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int u, v;
        init();
        for(int i=1; i<=m; ++i){
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        if(m==0){
            printf("0\n");
            continue;
        }
        ans = 1;
        for(int i=1; i<=n; ++i){
            if(!vis[i]){
                dfs(i, i);
            }
        }
        ans = (ans%mod*(quick_pow(2, (ll)m-num))%mod)%mod;//环外的边 2^k个方案, 可以全删 
        printf("%lld\n", ans);
    }   
}

而对于邻接表存的图,就不会WA,可以AC,为什么?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 3e5+100;
const int maxm = 5e5+100;
int n, m;
/*struct node{
    int to, next;
    node(){ }
    node(int a, int b):to(a), next(b){  }
};*/
//node edge[maxm];
//int head[maxn];
//int cnt;
ll num;
ll ans;
ll vis[maxn];
vector<int>G[maxn];
inline void init(){
    //memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    //cnt = 0;
    for(int i=0; i<maxn; ++i)G[i].clear(); 
    num=0;
}
ll quick_pow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1)res=(res*a%mod)%mod;
        a=(a*a)%mod;
        b>>=1;
    }//cout<<res<<endl;
    return res;
}
void addedge(int u, int v){

    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs(int u, int fa){
    vis[u]=vis[fa]+1;
    for(auto v:G[u]){
        if(v==fa)continue;
        if(!vis[v])dfs(v, u);
        else if(vis[u]>vis[v]){
            ll tmp = vis[u]-vis[v]+1;
            num += tmp;
            ans = (ans%mod*(quick_pow(2, tmp)-1)%mod)%mod;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int u, v;
        init();
        for(int i=1; i<=m; ++i){
            scanf("%d%d", &u, &v);
            addedge(u, v);
        }
        if(m==0){
            printf("0\n");
            continue;
        }
        ans = 1;
        for(int i=1; i<=n; ++i){
            if(!vis[i]){
                dfs(i, 0);
            }
        }
    //  cout << 1<<endl;
        ans = (ans%mod*(quick_pow(2, (ll)m-num))%mod)%mod;//环外的边 2^k个方案, 可以全删 
        printf("%lld\n", ans);
    }   
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题