我最开始用的清空原数组重建图,边数组开到6e6,其他是1e6,结果官方和民间数据最后四个点MLE和TLE,后面改了一下建图,用另一个数组存新图,点数组用5e5边用2e6炸了,后面一直提交,只改数组大小,提交记录改一次变一次,不是有点T了就是MLE或者WA,现在改到官方全过,民间最后四个点死活过不去,代码放下面,问一下各位大佬原因,也有可能是我的代码问题,有的话能不能帮忙指出一下,提交记录和源代码可以搜的到,我开了公开,最后一次的代码我放下面了
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
struct node
{
int to,next;
}e[6100101],e2[6100101];
int n,m,head[1000001],head2[1000001],tot=1,c[1000011],a[1000001];
int b[1000001],dcc[1000001],ans,dfn[1000001],low[1000001],id,siz[1000001];
ll f[1000001][2],mod=1e9+7,res;
inline void add(int u,int v)
{
e[++tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
inline void add2(int u,int v)
{
e2[++tot].next=head2[u];
e2[tot].to=v;
head2[u]=tot;
}
inline ll power(int x)
{
ll base=2,res=1;
while(x)
{
if(x&1) res=res*base%mod;
base=base*base%mod;
x>>=1;
}
return res;
}
inline void tarjan(int u,int in_edge)
{
dfn[u]=low[u]=++id;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v,i);
if(dfn[u]<low[v])
b[i]=b[i^1]=1;
low[u]=min(low[v],low[u]);
}
else
if(i!=(in_edge^1))
low[u]=min(dfn[v],low[u]);
}
}
void dfs(int u)
{
dcc[u]=ans;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dcc[v]||b[i]) continue;
dfs(v);
}
}
void dfss(int u,int fa)
{
siz[u]=c[u];
for(int i=head2[u];i;i=e2[i].next)
{
int v=e2[i].to;
if(v==fa) continue;
dfss(v,u);
siz[u]+=siz[v]+1;
}
}
void dp(int u,int fa)
{
for(int i=head2[u];i;i=e2[i].next)
{
int v=e2[i].to;
if(v==fa) continue;
dp(v,u);
f[u][1]=(f[u][1]*(((f[v][0]<<1)+f[v][1])%mod)%mod+f[u][0]*f[v][1]%mod)%mod;
f[u][0]=f[u][0]*((f[v][0]<<1)%mod)%mod;
}
if(u==1) res=(res+f[u][1])%mod;
else res=(res+f[u][1]*power(siz[1]-siz[u]-1))%mod;
}
int main()
{
std::cin.tie(0)->sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(x==y) continue;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
for(int i=1;i<=n;i++)
if(!dcc[i])
{
++ans;
dfs(i);
}
for(int i=1;i<=n;i++)
a[dcc[i]]++;
tot=1;
for(int u=1;u<=n;u++)
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dcc[u]==dcc[v]) c[dcc[u]]++;
else add2(dcc[u],dcc[v]);
}
for(int i=1;i<=ans;i++)
{
c[i]>>=1;
f[i][0]=power(c[i]);
f[i][1]=power(a[i]+c[i])-f[i][0];
}
dfss(1,0),dp(1,0);
cout<<res;
}