HDUOJ 4496 通化邀请赛重现 D-City

发布时间:2016-12-8 8:19:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDUOJ 4496 通化邀请赛重现 D-City",主要涉及到HDUOJ 4496 通化邀请赛重现 D-City方面的内容,对于HDUOJ 4496 通化邀请赛重现 D-City感兴趣的同学可以参考一下。

传送门 题意:一个图,问按顺序破坏边后的块数。 思路:边全部破坏后肯定是n块,想到可以从后往前推答案,于是简单的并查集就好了。 吐槽:多case,白wa了。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int f[10005]; int a[100005],b[100005]; int m,n; int ans[100005]; int num; int find(int i) { if(f[i]==i)return i; else { f[i]=find(f[i]); return f[i]; } } void go(int i) { int x=find(a[i]); int y=find(b[i]); if(x!=y) { num--; if(x<y)f[y]=x; else f[x]=y; } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1; i<=m; i++)scanf("%d%d",&a[i],&b[i]); for(int i=0; i<n; i++)f[i]=i; num=n; for(int i=m; i>0; i--) { ans[i]=num; go(i); } for(int i=1; i<=m; i++)printf("%d\n",ans[i]); } return 0; }

上一篇:个人开公司的流程,以后用得着(经典)
下一篇:android textview和edittext中插入表情

相关文章

相关评论