传送门
发这篇只是为了记录一个容易TLE的坑点：对于这种多组数据，所有数据n之和不超过3e5的题，初始化的时候要for 1 to n，而不能memset，否则比如30000组数据每组n为10，那么如果memset进行30000次的复杂度就会炸......
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const ll MOD=998244353; const int N=3e5+4; int n,m; struct Edge { int v,nxt; }e[N<<1]; int head[N],etot; bool ok; int mk[N]; int cnt[2][N]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void adde(int u,int v) { e[++etot].nxt=head[u],e[etot].v=v,head[u]=etot; } inline void init() { ok=true; etot=0; for (register int i=1;i<=n;++i) { head[i]=mk[i]=cnt[0][i]=cnt[1][i]=-1; } } inline void dfs(int p,int c,int id) { if (~mk[p]) { if (mk[p]^c) ok=false; return ; } mk[p]=c; ++cnt[c][id]; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; dfs(v,c^1,id); if (!ok) return ; } } inline ll fpow(ll a,ll b) { ll ret=1; while (b) { if (b&1) ret=ret*a%MOD; b>>=1,a=a*a%MOD; } return ret; } int main() { int kase=read(); while (kase--) { n=read(),m=read(); init(); for (register int i=0;i<m;++i) { int u=read(),v=read(); adde(u,v); adde(v,u); } for (register int i=1;i<=n;++i) if (mk[i]==-1) { cnt[0][i]=cnt[1][i]=0; dfs(i,0,i); if (!ok) break; } if (!ok) { puts("0"); continue; } ll ans=1; for (register int i=1;i<=n;++i) if (~cnt[0][i]) { ll x=fpow(2,cnt[0][i]); ll y=fpow(2,cnt[1][i]); (ans*=(x+y)%MOD)%=MOD; } printf("%lld\n",ans); } return 0; }
