题目描述
燃烧军团大举入侵艾泽拉斯，现以在艾星建立了大量的军事要塞，这些要塞通过若干个道路直接或间接连接。如果两个城市是连通的，那么它们处于同一连通块之中。现在抗魔联军发明了一种威力巨大的法术，每发动一次将会直接摧毁一个军事要塞，同时也摧毁与他相连的道路。每进行一次打击，联军需要知道未被摧毁的要塞的连通块数。联军会给出最初要塞的连通情况以及打击顺序，请快速计算每次打击之后未被摧毁的要塞的连通块数量。 输入
输入第一行为两个整数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<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 100000+10; const int MAXM = 200000; struct Edge { int from,to,nexts; }edge[MAXM<<2]; int head[MAXN],top; int pre[MAXN]; int n,m; void init(){ memset(head,-1,sizeof(head)); top=0; for(int i=0;i<=n;i++) pre[i]=i; } void addedge(int a,int b){ Edge e={a,b,head[a]}; edge[top]=e;head[a]=top++; } int Find(int x){ return x==pre[x]?x:pre[x]=Find(pre[x]); } void join(int a,int b){ a=Find(a);b=Find(b); if(a!=b) pre[a]=b; } int hit[MAXN]; map<int,bool>vis; map<int,int>M; int ans[MAXN]; void solve(){ for(int i=1;i<=m;i++){ int a,b; scanf("%d%d",&a,&b); addedge(a,b); addedge(b,a); } int k;cin>>k; for(int i=1;i<=k;i++) { scanf("%d",&hit[i]); vis[hit[i]] =1; } for(int now=1;now<=n;now++){ if(vis[now]) continue; for(int i=head[now];i!=-1;i=edge[i].nexts){ Edge e=edge[i]; if(vis[e.to]) continue; join(e.from,e.to); } } //puts("=========="); for(int i=1;i<=n;i++) { if(vis[i]) continue; M[Find(i)]++; } ans[k+1]=M.size(); // printf(" nas[k+1] %d\n",ans[k+1]); for(int now=k;now>=1;now--){ vis[hit[now]]=0; ans[now]=ans[now+1]+1;// 因为初始多一个点，肯定多一个联通快 for(int i=head[hit[now]];i!=-1;i=edge[i].nexts){ Edge e=edge[i]; if(vis[e.to]) continue; int t1=Find(e.from);int t2=Find(e.to); if(t1!=t2){ //合并一次，联通快肯定少一个 ans[now]--; pre[t1]=t2; } } } for(int i=1;i<=k+1;i++) printf("%d\n",ans[i]) ; } int main(){ scanf("%d%d",&n,&m); init(); solve(); return 0; }