并查集

正序处理时间复杂度为n^2，考虑逆序处理，这样，时间复杂度从n^2降为nlogn

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 400005int fa[N<<1],n,m,K,head[N<<1],cnt,q[N],ans[N];struct node{ int to,next;}e[N<<1];void add(int x,int y){ e[cnt].to=y; e[cnt].next=head[x]; head[x]=cnt++; return ;}int find(int x){ int p=x,t; while(fa[p]!=p)p=fa[p]; while(x!=p)t=fa[x],fa[x]=p,x=t; return p;}bool vis[N];int main(){ for(int i=1;i
            
             =0;i--) { ans[i]=ans[i+1]+1; for(int j=head[q[i+1]];j!=-1;j=e[j].next) { int to1=e[j].to; if(!vis[to1])continue; int fx=find(q[i+1]),fy=find(to1); if(fx!=fy) { fa[fx]=fy; ans[i]--; } } vis[q[i]]=1; } for(int i=0;i<=K;i++) { printf("%d\n",ans[i]); } return 0;}