问题 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。
接下来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;
}加油！！！努力！！！