取啥名好 @ 2019-10-24 18:59:18
#include<bits/stdc++.h>
using namespace std;
int n,m,k,tx,ty,cnt=0;
int jl[2000001]={0},mark[2000001]={0},fa[2000001]={0},ans[2000001]={0};
struct node{
int x,y;
}temp;
queue<node> q,qt,qk;
inline int r(){
int x=0,f=1;char c=getchar();
while(c<'0'||'9'<c) c=getchar();
while('0'<=c&&c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
n=r(),m=r();
for(int i=0;i<n;i++) fa[i]=i;
for(int i=1;i<=m;i++)temp.x=r(),temp.y=r(),q.push(temp);//存边到队列里
k=r();cnt=n-k;//现在的连通块数是全部的减去毁掉的
for(int i=1;i<=k;i++) jl[i]=r(),mark[jl[i]]=1;//毁掉的标记一下
for(int i=k;i>=1;i--){
while(!q.empty()){
temp=q.front();
qt.push(temp);//放到另一个队列里,
q.pop();
if(!mark[temp.x]&&!mark[temp.y]){//如果可以连
tx=find(temp.x),ty=find(temp.y);
if(tx!=ty){
fa[tx]=ty;
cnt--;//联通一个,所以连通块少一个
}
qt.pop();//把用掉的或没用的扔了,只留下现在用不了的
}
}
q=qt;//把没用过的放进去
qt=qk;//把这个清空
ans[i]=cnt;//记录答案
cnt++;//新建一个
mark[jl[i]]=0;//改成完好的
}
for(int i=1;i<=k;i++) cout<<ans[i]<<endl;
return 0;
}
by 取啥名好 @ 2019-10-24 18:59:34
已开大数组,不是数组问题
by Raging零 @ 2019-11-01 10:07:44
注意看题目,首先输出刚开始时联通快的数目
第一行是开始时星球的连通块个数。
接下来的 K 行,每行一个整数,表示经过该次打击后现存星球的连通块个数。