河南省多校联萌-HAUT-1285-军团再临

问题 G: 军团再临

时间限制: 1 秒   内存限制: 128 MB 提交: 48   解决: 19 提交  状态 

题目描述

燃烧军团大举入侵艾泽拉斯，现以在艾星建立了大量的军事要塞，这些要塞通过若干个道路直接或间接连接。如果两个城市是连通的，那么它们处于同一连通块之中。现在抗魔联军发明了一种威力巨大的法术，每发动一次将会直接摧毁一个军事要塞，同时也摧毁与他相连的道路。每进行一次打击，联军需要知道未被摧毁的要塞的连通块数。联军会给出最初要塞的连通情况以及打击顺序，请快速计算每次打击之后未被摧毁的要塞的连通块数量。

输入

输入第一行为两个整数n,m分别表示要塞个数和道路个数。1<=n<=100000,1<=m<=200000。 接下来m行每行两个整数x,y (1<=x,y<=n)表示要塞x和要塞y之间有一条道路连接。 接下来一行为一个整数k表示将会打击的要塞数量。1<=k<=n。 接下来k行每行一个整数v表示会打击的城市这k个数互不相同,1<=v<=n。

输出

第一行输出最初的连通块个数，后k行一次输出每次打击后的结果。

样例输入

8 13 1 2 2 7 7 6 6 1 1 7 2 3 3 4 4 5 5 6 8 2 8 3 8 7 4 7 5 2 7 4 6 8

样例输出

1 1 1 2 3 3

提示

提交  状态 

总结，自己还是太菜，看到数据长没人交就认为这到题难（其实还真算不简单）在听了学长说的后有点思路，但还不知道咋写，一看完标程瞬间明白，这是一道很水的并查集，可以倒着推。。。。。 自己对并查集还没太理解，不知道什么时候该用，不会活用。。。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<vector> using namespace std; int ss[400005]; vector<int>q[400005]; int vis[400005]={0}; int viss[400005]={0}; int hk[400005]={0}; int sum[400005]={0}; int find(int x) { if(x==ss[x]) return x; return ss[x]=find(ss[x]); } int main() { ios::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) ss[i]=i; for(int i=0;i<m;i++) { int x,y; cin>>x>>y; q[x].push_back(y); q[y].push_back(x); } int gj; cin>>gj; for(int i=1;i<=gj;i++) { cin>>hk[i]; vis[hk[i]]=1; } for(int i=1;i<=n;i++) { if(vis[i]) continue; for(int j=0;j<q[i].size();j++) { if(vis[q[i][j]]) continue; int xx=find(i); int yy=find(q[i][j]); if(xx!=yy) ss[xx]=yy; } } for(int i=1;i<=n;i++) { if(vis[i]) continue; int k=find(i); if(!viss[k]) { sum[gj+1]++; viss[k]=1; } } // cout<<ss[i]; for(int i=gj;i>=1;i--) { vis[hk[i]]=0; sum[i]=sum[i+1]; int flag=0; for(int j=0;j<q[hk[i]].size();j++) {// cout<<q[hk[i]][j]<<" "<<hk[i]<<vis[q[hk[i]][j]]<<endl; if(vis[q[hk[i]][j]]) continue; flag++; int xx=find(hk[i]); int yy=find(q[hk[i]][j]); if(xx!=yy) { if(hk[i]!=xx) sum[i]--; ss[xx]=yy; } } if(flag==0) sum[i]++; } for(int i=1;i<=gj+1;i++) cout<<sum[i]<<endl; return 0; }

加油！！！努力！！！