Количество компонент связности в графе можно вычислить, например, с помощью обхода в глубину. 2 Для этого нужно: 2

1. Запустить обход из первой вершины, и все вершины, которые он при этом обошёл, образуют первую компоненту связности. 2
2. Найти первую из оставшихся вершин, которые ещё не были посещены, и запустить обход из неё, найдя тем самым вторую компоненту связности. 2
3. И так далее, пока все вершины не станут помеченными. 2 После этого переменная будет хранить число компонент связности, а массив — номер компоненты для каждой вершины. 2

Также количество компонент связности можно найти, используя систему непересекающихся множеств. 3 Для этого нужно: 3

1. Изначально расположить каждую вершину в отдельном множестве. 3 Каждая вершина является представителем своего множества. 3
2. Далее для каждого ребра (u, v) объединить множества, содержащие u и v. 3
3. После обработки всех рёбер количество компонент связности будет равно числу множеств в системе непересекающихся множеств. 3