现在的位置: 首页 > 综合 > 正文

hdu4496

2014年08月29日 ⁄ 综合 ⁄ 共 534字 ⁄ 字号 评论关闭

从后面到前面,把破坏桥看成建立桥,之后连通的集合个数反序输出就可以了

#include<stdio.h>  
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>
#define maxn 100010
int n,m;
int fa[maxn],v[maxn],u[maxn],res[maxn];
int find(int x)
{
	return fa[x]==x?x:(fa[x]=find(fa[x]));
}
main()
{
	int i,num,a,b;
	//freopen("D:\\in.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		res[0]=num=n;
		for(i=0;i<n;i++)
			fa[i]=i;
		for(i=0;i<m;i++)
			scanf("%d%d",&u[i],&v[i]);
		for(i=m-1;i>=0;i--)
		{
			a=find(u[i]);
			b=find(v[i]);
			if(a!=b)
			{
				fa[a]=b;
				num--;
			}
			res[m-i]=num;
		}
		for(i=m-1;i>=0;i--)
			printf("%d\n",res[i]);
	}
	return 0;
}

抱歉!评论已关闭.