A. 无向图的连通分量 （已解蕨）

常规
1 
题目描述：
给出一个无向图，求图的连通分量的个数。保证无重边和自环。

 

输入格式：
第一行两个正整数 n（节点数），m（边数）。（节点编号从 1 到 n）

以下 m 行每行一个整数对描述一条边

 

输出格式：
一个整数表示连通分量的个数

 

样例输入：
8 7
1 2 
2 3
3 1
4 5
4 6
4 7
4 8
 

样例输出：
2
 

数据范围：
1 ≤ n, m ≤10000
2 个赞
2

dfs bfs 并查集均可

4 个赞
3

我用的dfs

3 个赞
4

那请你发代码让我们调。不然我们不知道如何帮助你

3 个赞
5

等等我再改一下

3 个赞
6

这道题的范围很大，可以排除邻接矩阵，所以，这道题可以使用邻接表；
邻接表的存储很简单，与邻接矩阵差不多(无向图)

邻接表的第一维是节点，第二维是此点对应的边集

for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		fec[x].push_back(y);
		fec[y].push_back(x);
	}

而要求连通分量的个数，则可以用dfs(深度优先搜索)来遍历每一个节点，如果遍历不下去，那么此连通分量已经遍历完，可以先把ans+1；

接着遍历下一个节点，先判断是否遍历，如果没有，重复第1个操作

最后，把ans输出就好

3 个赞
7

参考代码在私信

1 个赞
8

不用了，我自己琢磨出来了（喜

4 个赞
9

《CE》

3 个赞
10

666

3 个赞
11

其实是数组名字写错了 :smiling_face:
我看到了（喜

3 个赞