Xeqwq @ 2022-08-08 20:31:06
rt. 但是只有20分 而ruin数组用bool连样例都过不了
#include <iostream>
#include <vector>
using namespace std;
int n,m,k;
const int Maxn=100005;
int fa[Maxn];
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y)
{
fa[find(x)]=find(y);
}
vector<int> adj[Maxn];
int ord[Maxn];
int ruin[Maxn],ans[Maxn];
int f[Maxn];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) fa[i]=i;
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
cin>>k;
for(int i=1;i<=k;i++)
{
scanf("%d",&ord[i]);
ruin[ord[i]]=1;
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(ruin[i]) continue;
for(int j=0;j<adj[i].size();j++)
{
if(!ruin[adj[i][j]])
merge(adj[i][j],i);
}
}
for(int i=0;i<n;i++)
{
if(ruin[i]) continue;
if(!f[i])
{
f[i]=1;
cnt++;
}
}
ans[k+1]=cnt;
for(int i=k;i>=1;i--)
{
ruin[ord[i]]=0;
cnt++;
for(int j=0;j<adj[ord[i]].size();j++)
{
if(!ruin[adj[ord[i]][j]])
{
if(find(ord[i])!=find(adj[ord[i]][j]))
{
cnt--;
}
merge(ord[i],adj[ord[i]][j]);
}
}
ans[i]=cnt;
}
for(int i=1;i<=k+1;i++)
printf("%d\n",ans[i]);
}
by Xeqwq @ 2022-08-08 20:31:43
开大数组也只有40分
by xfrvq @ 2022-08-08 20:41:19
@Xeqwq 数组访问越界(大概)
by Xeqwq @ 2022-08-08 20:42:38
@OneZzz6174 哦哦 但为什么在数组开到了400005之后仍然有6个点wa(望dalao不吝赐教 感谢大佬