Подключенные компоненты BOOST переполнение стека

Если у меня есть график с 1 узлом и без ребер. количество подключенных компонентов = 1, верно?

Если у меня есть график с 2 узлами и без ребер. количество подключенных компонентов = 2, верно?

Если у меня есть график с 2 узлами и 1 ребрами. количество подключенных компонентов = 1, верно?

У меня есть этот кусок кода:

typedef adjacency_list <vecS, vecS, undirectedS> Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;

/* typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef property_map<Graph, vertex_index_t>::type IndexMap;

typedef std::pair<int,int> E;
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::out_edge_iterator edge_iter;
typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap;*/int main(int,char*[])
{

int num_nodes,num_edges;
cin >> num_nodes >> num_edges;

Graph g(num_nodes);

for(int i = 0;i < num_edges; i++) // i/p edges into graph g
{

int e1,e2;
cin >> e1 >> e2;

Edge e;
bool success;tie(e,success) = add_edge(e1, e2, g);
}

vector <int> components(num_nodes);
int num = connected_components(g, &components[0]);cout<<"moooooo"<<num<<endl;

для этих входов:

1 0

а также

2 0

а также

2 1

Я получаю соответственно

1

а также

2

а также

2

Зачем? разве это не будет 1 сейчас? Я неправильно понял подключенные компоненты?

Моя программа дает num = 2 для всех входов, мои входные данные следующие:

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 1

5 5
1 2
2 3
3 4
4 1
3 5

6 6
1 2
2 3
3 4
4 1
3 5
5 6

8 9
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 8
8 5

8 10
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 8
8 5
4 6

какой шпудл я делаю?

1

Решение

Связанный компонент — это подграф графа или сам граф, где мы можем
достичь всех узлов от каждого другого узла. Минимальное количество
подключенный компонент = 0, в то время как максимальное количество узлов
графика.

Проблема здесь заключалась в том, что я использовал узел, начинающийся с 1 …. и boost рассматривал узлы от 0, следовательно, я всегда получал на 1 подключенный компонент больше, чем обычно.

Трюк ::
это использовать vertice_num_ -1 вместо самого номера вершины.

2

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


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector