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

Пользователи вводят количество вершин (n), а затем — в следующих строках n — как вершины связаны, а именно, что число x в i-й строке означает, что вершина i соединена с вершиной x (граф неориентированный). Задача состоит в том, чтобы найти количество компонент связности в этом графе, а мой код - я почему-то не могу найти - выдает неправильные значения (например, при вводе 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;

}

c++ graph connected-components depth-first-search
person VanDerWarden    schedule 19.02.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В вашем коде есть путаница между счетчиком 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;

        }

Затем работает, как ожидалось.

Онлайн-демонстрация

person Christophe    schedule 19.02.2016
comment
@hetajr Чтобы избежать каких-либо сомнений, я обновил онлайн-демонстрацию, чтобы отобразить график и показать группы, идентифицированные с исправленной версией алгоритма. - person Christophe; 19.02.2016