1 #include<iostream> 2 using namespace std; 3 const int N=4e5+100; 4 struct edge 5 { 6 int from; 7 int to; 8 int nex; 9 }; 10 edge a[N]; 11 int head[N]; 12 int cnt=0; 13 //以上是链式向前星存储图 14 int fa[N];//并查集 15 bool used[N];//每个点是否被摧毁 16 int node[N];//被摧毁的 17 int ans[N];//答案 18 void init(int n) 19 { 20 for(int i=0;i<n;i++) 21 { 22 fa[i]=i;//并查集 23 used[i]=0; 24 head[i]=-1; 25 } 26 } 27 void add(int b,int c)//边的计数从0开始 28 { 29 a[cnt].from=b; 30 a[cnt].to=c; 31 a[cnt].nex=head[b]; 32 head[b]=cnt; 33 cnt++; 34 } 35 int finds(int x) 36 { 37 while(fa[x]!=fa[fa[x]]) 38 { 39 fa[x]=fa[fa[x]]; 40 } 41 return fa[x]; 42 } 43 int main(void) 44 { 45 int n,m; 46 cin>>n>>m; 47 init(n);//初始化 48 for(int i=1;i<=m;i++) 49 { 50 int a,b; 51 cin>>a>>b; 52 add(a,b);//无向图 53 add(b,a); 54 } 55 int k; 56 cin>>k; 57 for(int i=0;i<k;i++)//被摧毁的顺序，反过来就是重建的顺序 58 { 59 cin>>node[i]; 60 used[node[i]]=1;//标记为已打击 61 } 62 int total=n-k;//假设全部的边都不存在，那么所有打击完成之后，所剩的联通分量就是n-k 63 //以下计算打击完成后的连通分量数 64 for(int i=0;i<2*m;i++)//遍历所有的边 65 { 66 if(used[a[i].from]==0&&used[a[i].to]==0)//如果都没有被打击 67 { 68 if(finds(a[i].from)!=finds(a[i].to))//且在此前没有被连接在一起 69 { 70 total--; 71 fa[finds(a[i].from)]=finds(a[i].to); 72 } 73 } 74 } 75 ans[k]=total; 76 for(int i=k-1;i>=0;i--) 77 { 78 int t=node[i]; 79 total++; 80 used[t]=0;//已修复，没有被打击 81 for(int i=head[t];i!=-1;i=a[i].nex)//遍历修复的点的全部边 82 { 83 if(used[a[i].to]==0&&finds(t)!=finds(a[i].to))//如果可以连而且还没连 84 { 85 total--; 86 fa[finds(t)]=finds(a[i].to); 87 } 88 } 89 ans[i]=total; 90 } 91 for(int i=0;i<=k;i++) 92 { 93 cout<<ans[i]<<endl; 94 } 95 return 0; 96 }
让你确定每次打击之后还有多少个联通分量（并查集似乎顺着做不了），就只有逆着来做了
首先假设所有将要打击的点都被破坏，然后再一步一步重建，这就是正常的并查集了，但是链式向前星挺难的