Нахождение количества связанных компонентов в неориентированном графе

Пользователь вводит количество вершин (N) а затем — в следующем N линии — как связаны вершины, а именно, что число Икс в я-эта строка означает, что вершина я связан с вершиной Икс (график ненаправленный). Задача состоит в том, чтобы найти количество подключенных компонентов в этом графике, и мой код — по какой-то причине я не могу найти — выводит неправильные значения (например, с вводом 4 2 1 2 4, мой код выводит 4 вместо 2). Любая помощь с благодарностью.

#include <iostream>
#include <vector>
#include <stack>

int n;

using namespace std;
vector <int> graph[1000006];
int components[1000006];
int no_of_components;
stack <int> mystack;

int main(){

cin >> n;

for (int i=0; i<n; i++){
int X;
cin >> X;
graph[X-1].push_back(i);
}

for (int i=0; i<n; i++){

if (components[i]>0) continue;

no_of_components++;

mystack.push(i);
components[i]=no_of_components;

while (mystack.empty()==false){
int v;

v=mystack.top();
mystack.pop();

for (int u=0; u<graph[v].size(); u++){
if (components[u]>0) continue;

mystack.push(u);
components[u]=no_of_components;

}
}
}

cout << no_of_components;

return 0;

}

1

Решение

В вашем коде есть путаница между счетчиком u который позволяет перебирать соединения узла v и сами соединения:

  • v это узел
  • graph[v] вектор связей
  • u индекс в векторе соединений
  • так graph[v][u] это узел, связанный с v а также component[graph[v][u]] маркер компонента, который вы должны обновить

Поэтому вы должны исправить внутренний цикл for следующим образом:

        for (int u=0; u<graph[v].size(); u++){
if (components[graph[v][u]]>0) continue;

mystack.push(graph[v][u]);
components[graph[v][u]]=no_of_components;

}

Тогда работает как положено.

Онлайн демо

1

Другие решения

Других решений пока нет …