# component that node i is in

1 function flood_fill(new_component)

2 do

3 num_visited = 0

4 for all nodes i

5 　if component(i) = -2

6 　num_visited = num_visited + 1

7 　component(i) = new_component

8 　for all neighbors j of node i

9 　if component(j) = nil

10　 component(j) = -2

11 　until num_visited = 0

12 function find_components

13 　num_components = 0

14 for all nodes i

15　 component(node i) = nil

16 for all nodes i

17 　if component(node i) is nil

18 　num_components =

num_components + 1

19 　component(i) = -2

20　 flood_fill(component num_components)

可以用深度优先遍历，广度优先遍历和广度优先扫描（速度很慢）来实现，上面代码实现的是广度优先扫描

其它算法的详细实现如下：

深搜：取一个结点，对其标记，然后标记它所有的邻结点。对它的每一个邻结点这么一直递归下去完成搜索。

广搜：与深搜不同的是，广搜把结点加入队列中。

广度扫描（不常见）：每个结点有两个值，一个用来记录它属于哪个连通子图（c），一个用来标记是否已经访问（v）。算法对每一个未访问而在某个连通子图当中的结点扫描，将其标记访问，然后把它的邻结点的（c）值改为当前结点的（c）值。

深搜最容易写，但它需要一个栈。搜索显式图没问题，而对于隐式图，栈可能就存不下了。

广搜稍微好一点，不过也存在问题。搜索大的图它的队列有可能存不下。深搜和广搜时间复杂度均为O(N+M)。其中，N为结点数，M为边数。

广度扫描需要的额外空间很少，或者可以说根本不要额外空间，但是它很慢。时间复杂度是O(N^2+M)

节点变化如下（没有显示即值为nil，左边是节点编号，右边是Component的值）

第一步

1 -2

第二步

1 1

4 -2

第三步

1 1

4 1

8 -2

第四步

1 1

4 1

8 1

第一次扫描结束，下面找到第一个nil的节点2，继续扫描

第五步

1 1

2 -2

4 1

8 1

第六步

1 1

2 2

4 1

7 -2

8 1

9 -2

第七步

1 1

2 2

4 1

5 -2

7 2

8 1

9 -2

第八步

1 1

2 2

4 1

5 -2

7 2

8 1

9 2

第九步

1 1

2 2

4 1

5 2

6 -2

7 2

8 1

9 2

第十步

1 1

2 2

4 1

5 2

6 2

7 2

8 1

9 2

没有-2的节点了，下面继续寻找nil节点，找到3

第11步

1 1

2 2

3 -2

4 1

5 2

6 2

7 2

8 1

9 2

第12步

1 1

2 2

3 3

4 1

5 2

6 2

7 2

8 1

9 2