我们可以通过下面的例子来更好的了解一下深度优先搜索。
对于这个联通块,蓝色节点代表未被访问的节点,黑色代表节点已被访问的节点,黄色边框代表当前节点的邻居节点。
假设我们从节点2开始,我们需要做的就是把这个联通块所有的节点打上一个标记
给定一张无向图,图中的每个节点用一个整数编号,且图通过邻接表存储。请你计算该图中有多少个连通块。我们定义一个连通块是一个图的最大子图,在这个子图中任意两个节点都有路径相连。换句话说,连通块是一个连通的无向图的部分,其中任意两个节点通过一系列边相互连接。
第一行包含两个整数 n 和 m,表示图中有 n 个节点(编号为 1,2,…,n),m 条边。接下来的 m 行,每行包含两个整数 u 和 v,表示存在一条无向边连接节点 u 和节点 v。
输出一个整数,表示图中的连通块数量。
5 3
1 2
2 3
4 5
2