Найти связанные компоненты в графике

Ответ 1

Использовать поиск по глубине (DFS) для отметки всех отдельных подключенных компонентов по мере посещения:

dfs(node u)
  for each node v connected to u :
    if v is not visited :
      visited[v] = true
      dfs(v)


for each node u:
  if u is not visited :
    visited[u] = true
    connected_component += 1
    dfs(u)

Лучший способ - использовать этот простой метод, который является линейным временем O (n).
Поскольку вы спросили об алгоритме объединения-поиска:

for each node parent[node] = node  

for each node u :
   for each node v connected to u :  
       if findset(u)!=findset(v) :
           union(u,v)  

**I assume you know about how findset and union works **  
for each node if (parent[node] == node)  
    connected_component += 1

Ответ 2

Для каждого edge(u,v) найдите union(u,v), используя быстродействующую структуру данных поиска и найдите множество каждой вершины, используя find(v). Каждый новый набор является связным компонентом в графе