Если у меня есть график с 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
какой шпудл я делаю?
Связанный компонент — это подграф графа или сам граф, где мы можем
достичь всех узлов от каждого другого узла. Минимальное количество
подключенный компонент = 0, в то время как максимальное количество узлов
графика.
Проблема здесь заключалась в том, что я использовал узел, начинающийся с 1 …. и boost рассматривал узлы от 0, следовательно, я всегда получал на 1 подключенный компонент больше, чем обычно.
Трюк ::
это использовать vertice_num_ -1
вместо самого номера вершины.