【图论】求连通分量_【问题描述】 根据输入的图的邻接矩阵a,判断此图的连通分量的个数。 【输入形式】

Description

求一个图的连通分量

Input

$n$ 顶点数($n$<=$100$)
边

Output

连通分量

Sample Input

8
6 3
1 2
2 5
5 4
4 1
8 7
0 0
1
2
3
4
5
6
7
8

Sample Output

4
1

思路

这里有五种方法，分别是$dfs+邻接表，bfs+邻接表,dfs+邻接矩阵,bfs+邻接矩阵,bfs+邻接表+STL（队列）。$
首先是两种读入：

邻接表

 struct whw
{
   
	int x,y;
}a[10001];
/*---------------------------------------------------------*/
	scanf("%d%d",&x,&y);
	while (x && y)
	{
   
	    a[++m]=(whw){
   y,h[x]};h[x]=m;
	    a[++m]=(whw){
   x,h[y]};h[y]=m;//因为是无向图，所以x到y和y到x都要赋值
		scanf("%d%d",&x,&y);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

邻接矩阵

int h[1005][1005];
/*---------------------------------------------------------*/
	scanf("%d%d",&x,&y); 
	while (x && y)
	{
   
	    h[x][y]=h[y][x]=1;//上面
		scanf("%d%d",&x,&y);
	}
1
2
3
4
5
6
7
8
9

---

还有用$STL$时要注意：
库:$<queue>$
定义int类型的队列（wh）： q u e u e &lt; i n t