Derpy @ 2019-10-10 20:16:24
只有40分,WA了六个点(4,5,6,7,8,9)
#include<bits/stdc++.h>
#define mx 200005
using namespace std;
inline int r()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct node
{
int x,y;
};
vector<int>v[mx<<1];
int fa[mx<<1];
node q[mx<<1];
int d[mx<<1];
bool mark[mx<<1];
int fid(int x)
{
return fa[x]=fa[x]==x?x:fid(fa[x]);
}
int main()
{
int n=r(),m=r();
for(int i=1;i<=n;i++) fa[i-1]=i-1;
for(int i=1;i<=m;i++)
{
q[i].x=r();
q[i].y=r();
v[q[i].x].push_back(q[i].y);
v[q[i].y].push_back(q[i].x);
}
int k=r();
for(int i=1;i<=k;i++)
{
d[i]=r();
mark[d[i]]=1;
}
int ans=n-k;
for(int i=1;i<=m;i++)
{
if(!mark[q[i].x]&&!mark[q[i].y])
{
if(fid(q[i].x)==fid(q[i].y))
{
continue;
}
else
{
fa[fid(q[i].x)]=fid(q[i].y);
}
}
}
stack<int>dx;
dx.push(ans);
for(int i=k;i>=1;i--)
{
ans++;
int now=d[i];
mark[now]=0;
for(int j=1;j<=v[now].size();j++)
{
int to=v[now][j-1];
if(!mark[to])
{
if(fid(now)!=fid(to))
{
ans--;
}
fa[fid(now)]=fid(to);
}
}
dx.push(ans);
}
while(!dx.empty())
{
cout<<dx.top()<<endl;
dx.pop();
}
return 0;
}
by Derpy @ 2019-10-11 07:41:07
破案了,@暮光闪闪 太强了