求连通分量（图论练习题）

Description

求一个图的连通分量

Input

n 顶点数(<=100)
边

Output

连通分量

Sample Input

5
1 2
3 4
2 3
0 0

Sample Output

4

思路

用bfs遍历整张图。

代码

#include<cstdio>
using namespace std;
bool b[101][101];//b表示两条边是否连通
bool a[101];//a表示这个点是否被搜过
int n;int o,k,ans,maxn;
int max(int x,int y)//不解释
{
	return x>y?x:y;
}
int bfs(int x)//从x点开始遍历
{
	if (a[x]) return a[x];//如果已经遍历过，直接返回
	int state[101],father[101],head=0,tail=1;state[1]=x;maxn=a[x]=1;//初始化，连通分量最少也是1
	do
	{
		head++;
		for (int i=1;i<=n;i++)//遍历每个点
		 if (b[state[head]][i]&&!a[i])//如果这条边可以到达那个点，且那个点没被走过
		  {
		  	tail++;//队首加一
		  	father[tail]=head;//广搜习惯，father数组不要也行
		  	state[tail]=i;//入队
		  	a[i]=a[state[head]]=1;//封点
		  	b[state[head]][i]=false;//封路
		  	maxn++;//累加
		  }
    }while(head<tail);
    return maxn;//返回
}
int main()
{
	scanf("%d\n",&n);
	while (scanf("%d %d",&o,&k),b[o][k]=true,b[k][o]=true,o!=0&&k!=0);
	for (int i=1;i<=n;i++)
	 ans=max(ans,bfs(i));//取下所有连通分量的最大值
	printf("%d",ans);
}