在用前向星存图并遍历的时候,会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);
}
}