【BZOJ 1015】スターウォーズ並査集
2159 ワード
私はそこで顶と桥を切りたいのですが、あなたは私にこれが调査集で、人と人の间の信頼だと教えてくれました...
オフライン逆順操作は、削除されていないすべての点のサブマップを並べてセットし、逆順に点を加えるだけです.
オフライン逆順操作は、削除されていないすべての点のサブマップを並べてセットし、逆順に点を加えるだけです.
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 400005
using namespace std;
void _read(int &x)
{
x=0; char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return ;
}
void _readLL(long long &x)
{
x=0; char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return ;
}
struct edge
{
int to,next;
}e[maxn*4];
bool v[maxn];
int cnt,n,m,k,head[maxn],edge_ct,f[maxn],a[maxn];
int Find(int x)
{
if(f[x]==x)return x;
else return f[x]=Find(f[x]);
}
void add(int x,int y)
{
e[++edge_ct]=(edge){y,head[x]}; head[x]=edge_ct;
return ;
}
void Init()
{
_read(n); _read(m);
int x,y;
for(int i=1;i<=m;i++)
{
_read(x); _read(y);x++; y++;
add(x,y); add(y,x);
}
_read(k);
for(int i=1;i<=k;i++)
{_read(a[i]);
a[i]++;v[a[i]]=1;}
for(int i=1;i<=n;i++)f[i]=i;
cnt=n-k;
for(int i=1;i<=n;i++)if(!v[i])
{
for(int id=head[i];id;id=e[id].next)if(!v[e[id].to])
{
if(Find(i)!=Find(e[id].to))
{
cnt--; f[Find(i)]=Find(e[id].to);
}
}
}
return ;
}
int ans[maxn];
char s[35];int ct;
void out(int t)
{
if(!t)
{putchar('0'); putchar('
');return ;}
cnt=0;
while(t){s[++ct]=t%10+'0'; t=t/10;}
while(ct){putchar(s[ct]); ct--;}
putchar('
');
return;
}
void work()
{
for(int i=k;i>=0;i--)
{
ans[i]=cnt;
if(i==0)break;
for(int id=head[a[i]];id;id=e[id].next)if(!v[e[id].to])
{
if(Find(a[i])!=Find(e[id].to))
{
cnt--; f[Find(a[i])]=Find(e[id].to);
}
}
v[a[i]]=false;cnt++;
}
for(int i=0;i<=k;i++)
{
out(ans[i]);
}
return;
}
int main()
{
//freopen("in.txt","r",stdin);
Init();
work();
return 0;
}