[JSOI2008][TYVJ P1824] 星球大战
描述
考虑到邪恶的帝国完全有能力在短时间内制造出“死亡星球”的替代品,为了避免被一次全部歼灭,反抗军的指挥官决定把部队分散在很多星球上。可是,这样会带来通讯上的问题。某些星球之间可以通过“以太”隧道直接通讯,而没有隧道相连的星球之间的通讯就需要其他星球帮忙转发。因此,只有两个星球之间存在一条由“以太”隧道拼接成的路径,它们才可以正常通讯。
银河历2008年4月1日凌晨,反抗军最担心的事情还是发生了。反抗军司令部收到间谍的秘密通知:帝国军成功制造出第二代“死亡星球”,并将依次摧毁如下星球(星球列表略)。指挥官希望迅速计算出每次攻击之后通讯网络的连通情况,即反叛军所占据的星球被分成了多少个连通支,从而帮助决定在何时发动反击。
输入格式
接下来的M行,每行包含两个整数X和Y (0 ≤ X ≠ Y < N),表示星球X和星球Y之间有“以太”隧道,可以直接通讯。
接下来的一行包含一个整数K,表示将遭受攻击的星球的数目。
接下来的K行,每行一个整数,按照顺序列出了帝国军的攻击目标。这K个数互不相同,且都在0到N – 1的范围内。
输出格式
第一个整数表示开始时通讯网络的连通支个数。
接下来的第I (1 ≤ I ≤ K)个整数,表示在攻击列表上的第I个星球被摧毁后,通讯网络的连通支个数。
测试样例1
输入
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
输出
1
1
1
2
3
3
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int head[400001],next[400001],list[400001],a[400001],f[400001],ans[400001],n,m,k,sum,x,p,q,y,rest; bool visit[400001]; int read() { char c=getchar(); int a=0; while (c<‘0‘||c>‘9‘) c=getchar(); while (c>=‘0‘&&c<=‘9‘) { a=a*10+c-‘0‘; c=getchar(); } return a; } int find(int i) { int j=i,k=i,t; while (f[j]!=j) j=f[j]; while (f[k]!=k) { t=k; k=f[k]; f[t]=j; } return j; } void insert(int x,int y) { sum++; next[sum]=head[x]; head[x]=sum; list[sum]=y; } int main() { n=read(); m=read(); sum=0; for (int i=1;i<=m;i++) { x=read(); y=read(); insert(x,y); insert(y,x); } k=read(); memset(visit,1,sizeof(visit)); for (int i=1;i<=k;i++) { a[i]=read(); visit[a[i]]=0; } for (int i=0;i<n;i++) f[i]=i; rest=n-k; for (int i=0;i<n;i++) if (visit[i]) { x=head[i]; while (x!=0) { if (visit[list[x]]) if (find(i)!=find(list[x])) { f[find(i)]=find(list[x]); rest--; } x=next[x]; } } ans[k+1]=rest; for (int i=k;i>=1;i--) { visit[a[i]]=true; rest++; p=find(a[i]); x=head[a[i]]; while (x!=0) { if (visit[list[x]]) { q=find(list[x]); if (p!=q) { f[q]=p; rest--; } } x=next[x]; } ans[i]=rest; } for (int i=1;i<=k+1;i++) printf("%d\n",ans[i]); return 0; }
#2: Accepted (686ms, 10548KiB)
#3: Accepted (171ms, 10544KiB)
#5: Accepted (561ms, 10544KiB)
#7: Accepted (140ms, 10544KiB)
#8: Accepted (748ms, 10548KiB)
#9: Accepted (670ms, 10548KiB)
PS:
最好用非递归并查集。
规模较大,建议使用读入优化。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。