Пользователь вводит количество вершин (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;
}
В вашем коде есть путаница между счетчиком 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;
}
Тогда работает как положено.
Других решений пока нет …