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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
  vector<vector<int>> g(n);
  vector<vector<int>> graph(vertexCount);
  vector<int> visited(n); // не были в вершине - 0, иначе - номер её компоненты
  vector<int> visited(n); // не были в вершине - 0, иначе - номер её компоненты
   
   
  void dfs(int v, int component) {
  void dfs(int v, int component) {
     visited[v] = component;
     visited[v] = component;
     for (int to : g[v])
     for (int to : graph[v])
         if (!visited[to])
         if (!visited[to])
             dfs(to, component);
             dfs(to, component);
  }
  }
   
   
  int componentsCount = 0;
  int componentCount = 0;
  for (int i = 0; i < n; i++)
  for (int v = 0; v < vertexCount; v++)
     if (!visited[i])
     if (!visited[v])
         dfs(i, ++componentsCount);
         dfs(i, ++componentCount);


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

Версия от 21:05, 7 апреля 2021

vector<vector<int>> graph(vertexCount);
vector<int> visited(n); // не были в вершине - 0, иначе - номер её компоненты

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

int componentCount = 0;
for (int v = 0; v < vertexCount; v++)
    if (!visited[v])
        dfs(i, ++componentCount);

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

Ссылки

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