Компоненты связности: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 9: Строка 9:
  for (int v = 0; v < graph.size(); v++)
  for (int v = 0; v < graph.size(); v++)
     if (!visited[v])
     if (!visited[v])
         dfs(v, ++componentCount);
         dfs(graph, v, visited, ++componentCount);


== Ссылки на задачи ==
== Ссылки на задачи ==

Версия от 18:07, 22 марта 2022

void dfs(vector<vector<int>> &graph, int v, vector<int> &visited, int component) {
    visited[v] = component;
    for (int to : graph[v])
        if (!visited[to])
            dfs(graph, to, visited, component);
}

int componentCount = 0;
for (int v = 0; v < graph.size(); v++)
    if (!visited[v])
        dfs(graph, v, visited, ++componentCount);

Ссылки на задачи

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Компоненты_связности&oldid=2766