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);
    }   
}
c++
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问