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

Текущая версия от 15:14, 24 мая 2023

TLDR

Код

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);

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

Ссылки

@@ Строка 1: / Строка 1: @@
- vector<vector<int>> g(n);
+== TLDR ==
- vector<int> visited(n); // не были в вершине - 0, иначе - номер её компоненты
+<youtube width="300" height="180">rZkauRhHKGo</youtube>
+<youtube width="300" height="180">waXBVBKdV1s</youtube>
-  void dfs(int v, int component) {
+== Код ==
+  void dfs(vector<vector<int>> &graph, int v, vector<int> &visited, int component) {
       visited[v] = component;
-      for (int to : g[v])
+      for (int to : graph[v])
           if (!visited[to])
-              dfs(to, component);
+              dfs(graph, to, visited, component);
   }
-  int componentsCount = 0;
+  int componentCount = 0;
-  for (int i = 0; i < n; i++)
+  for (int v = 0; v < graph.size(); v++)
-      if (!visited[i])
+      if (!visited[v])
-          dfs(i, ++componentsCount);
+          dfs(graph, v, visited, ++componentCount);
 == Ссылки на задачи ==

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

Текущая версия от 15:14, 24 мая 2023

Содержание

TLDR

Код

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

Ссылки

Навигация

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

Текущая версия от 15:14, 24 мая 2023

TLDR

Код

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

Ссылки

Навигация

Поиск