1

(2 ответов, оставленных в Algo)

Я так понимаю можно модифицировать bfs/dfs ? как ? smile

2

(4 ответов, оставленных в Algo)

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

3

(4 ответов, оставленных в Algo)

Вот в этом коде
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

(4 ответов, оставленных в Algo)

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