[JSOI2008]星球大战starwar 【并差集】【逆序处理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1015
【算法分析】
就是逆过来，把拆分变成合并，用并差集即可。
【其它】= =1RE。n<=2m我还以为是他搞错了压在一起。。。
【CODE】
#include #include #include using namespace std;
const int N=405555;
struct edge{int y;edge *next;}g[405555],*ls[N];
int n,m,ans,e,Qn;
int F[N],Num[N],Q[N],v[N],reply[N];

inline void addedge(int x,int y){
g[++e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

int GF(int k){
int res,i,tmp;
for (i=k;F[i]!=i;i=F[i]);
res=i;
for (i=k;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
return res;
}

int main(){
e=0;
memset(ls,0,sizeof(ls));
memset(v,0,sizeof(v));
int x,y,i;
scanf("%d%d",&n,&m);
for (i=0;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=0;i F[i]=i;
Num[i]=1;
}
scanf("%d",&Qn);
ans=n;
for (i=0;i scanf("%d",&Q[i]);
if (!v[Q[i]]) ans–;
v[Q[i]]++;
}
for (i=0;i for (edge *t=ls[i];t;t=t->next)
if (!v[t->y] && GF(i)!=GF(t->y)){
ans–;
x=F[i]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
reply[Qn]=ans;
for (i=Qn-1;i>=0;i–){
v[Q[i]]–;
if (!v[Q[i]]){
ans++;
for (edge *t=ls[Q[i]];t;t=t->next)
if (!v[t->y] && GF(Q[i])!=GF(t->y)){
ans–;
x=F[Q[i]]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
}
reply[i]=ans;
}
for (int i=0;i<=Qn;i++) printf("%dn",reply[i]);
}