连通分支

并查集+图的传递闭包求连通分支

Author: 九天

C语言代码

#include "stdio.h"
int map[201][201];
int f[201],r[201],ceshi[201];
//并查集 路径压缩+rank合并
int father(int x)
{
	if(f[x]!=x)
		f[x]=father(f[x]);
	return f[x];
}
int link(int x,int y)
{
	x=father(x);y=father(y);
	if (r[x]>r[y])
	{
		f[y]=x;
	}
	else f[x]=y;
	if (r[x]==r[y])
	{
		r[y]++;
	}
	return 0;
}
int main()
{
	int i,j,k,n,num=0;
	memset(map,0,sizeof(map)); //初始化数组
	memset(r,0,sizeof(r));
	memset(ceshi,0,sizeof(ceshi));
	scanf("%d",&n);           //读入节点数
	for (i=1;i<=n;i++)         //读入边
	{
		f[i]=i;
		scanf("%d",&j);
		while (j!=0)
		{
			map[i][j]=1;
			scanf("%d",&j);
		}
	}
	for (k=1;k<=n;k++)            //求图的传递闭包
	{
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=n;j++)
			{
				map[i][j]=map[i][j]||(map[i][k]&&map[k][j]);
			}
		}
	}
	for (i=1;i<=n;i++)        //并查集 合并边
	{
		for (j=1;j<=n;j++)
		{
			if(map[i][j]==1&&map[j][i]==1)
				link(i,j);
		}
	}
	for (i=1;i<=n;i++)       //统计边集数目
	{
		ceshi[f[i]]++;
	}
	for (i=1;i<=n;i++)
		if (ceshi[i]!=0)
		{
			num++;
		}
	printf("%d",num);
	return 0;
}