hdu 4496 (并差集)

题意：给出一个图，m条边，输出删除前i条边后该图的联通块的个数。

思路：刚开始想着是不是联通问题，后来看明白题意后知道，如果从最后一条边添加的话，答案就会出来了，就是并差集的操作。

#include<stdio.h>

#include<string.h>

const int N=11000;

int f[N],sum,a[N*10];

struct edge

{

	int st,ed;

}e[N*10];

int find(int a)

{

    if(a!=f[a])

        f[a]=find(f[a]);

    return f[a];

}

int main()

{

	int i,n,m,x,y;

	while(scanf("%d%d",&n,&m)!=-1)

	{

		for(i=1;i<=m;i++)

		{

			scanf("%d%d",&e[i].st,&e[i].ed);

			e[i].st++;e[i].ed++;

		}

		a[m]=n;sum=n;

		for(i=1;i<=n;i++)

		  f[i]=i;

		for(i=m;i>1;i--)

		{

			x=find(e[i].st);

			y=find(e[i].ed);

			if(x!=y)

			{

				f[x]=find(y);

				sum--;

			}

			a[i-1]=sum;

		}

		for(i=1;i<=m;i++)

			printf("%d\n",a[i]);

	}

	return 0;

}

巴特西

hdu 4496 (并差集)

最新文章

热门文章