1

Тема: Поиск компонент связности

Алгоритм с сайта работает не так как надо sad Или у меня руки кривые
Можно простой пример его работы ?

2

Re: Поиск компонент связности

paul пишет:

Алгоритм с сайта работает не так как надо sad Или у меня руки кривые
Можно простой пример его работы ?

Если что-то конкретно непонятно - спросите, возможно вам помогут. Алгоритм довольно простой, попробуйте нарисовать граф на бумажке и просимулировать его работу на нем.

3

Re: Поиск компонент связности

Вот в этом коде
http://e-maxx.ru/algo/connected_components
меня смущает вот этот цикл
for (vector<int>::iterator i=g[cur].begin(); i!=g[cur].end(); ++i)
       if (!used[*i]) {
    used[*i] = true;
    q[t++] = *i;
    cout << ", " << *i;
       }

насколько я понимаю в g хранятся 0 и 1 показывающие связаны ли вершины ребрами, тогда в used[] мы обращаемся только по индексам 0 и 1.
Т. е. например есть матрица смежности
0 1 1
1 0 0
1 0 0
этот код выведет :
  Components :
  [ 0, 1]
  [ 2]
хотя должно получиться (как я понимаю)
  Components :
  [ 0, 1, 2]

Решил эту проблему переписыванием выше упомянутого цикла на :
            for(int j = 0; j<n; j++)
                    if (g[cur][j] == 1 && !used[j]) {
                        used[j] = true;
                        q[t++] = j;
                        cout << ", " << j;
                    }
Подскажите я не правильно понял код или что?

4

Re: Поиск компонент связности

Нет, в массиве g хранятся не 0 или 1, а списки смежных вершин. То есть g[v] это список всех вершин, которые смежные с v.

5

Re: Поиск компонент связности

ну тогда все понятно! спасибо)