Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
sven_mp
0 / 0 / 0
Регистрация: 08.04.2016
Сообщений: 12
#1

В неориентированном графе посчитать количество компонент связности - C++

18.04.2016, 21:35. Просмотров 119. Ответов 0
Метки нет (Все метки)

#include <iostream>
#include <fstream>

int components( int N, int *edges, int M )
{
int *rep = new int [ N ];

for ( int i = 0; i < N; ++i )
rep[ i ] = i;

for ( int i = 0, p, q; i < 2 * M; i += 2 )
{
for ( p = edges[ i ]; p != rep[ p ]; p = rep[ p ] );
for ( q = edges[ i + 1 ]; q != rep[ q ]; q = rep[ q ] );

if ( p == q ) continue;
rep[ p ] = q;
}

int cnt = 0;

// здесь надо вставить код для поиска количества компонент

return cnt;
}

int main()
{
std::ifstream ifs( "input.txt" );
std::ofstream ofs( "output.txt" );

if ( !ifs || !ofs )
return 1;

int N, M;
int *edges;
int cnt;

ifs >> N >> M;
edges = new int [ 2 * M ];

for ( int i = 0; i < 2 * M; i += 2 )
{
ifs >> edges[ i ] >> edges[ i + 1 ];
--edges[ i ];
--edges[ i + 1 ];
}

cnt = components( N, edges, M );
std::cout << cnt << std::endl;
ofs << cnt << std::endl;

return 0;
}

Добавлено через 3 минуты
не знаю что написать вместо комментариев, помогите пожалуйста
input.txt
1 2
2 3
4 2
5 6
7 8
output.txt
3
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2016, 21:35
Я подобрал для вас темы с готовыми решениями и ответами на вопрос В неориентированном графе посчитать количество компонент связности (C++):

В неориентированном графе посчитать количество компонент связности - C++
2. Компоненты связности В неориентированном графе посчитать количество компонент связности. В графе нет петель и кратных ребер. Формат...

Нужно немного переделать программу нахождения компонент сильной связности в графе - C++
В общем задание такое, нужно переделать эту программу, я не знаю как это сделать, помогите люди добрые)) #include &lt;iostream&gt; ...

Абсолютные медианы на неориентированном графе - C++
Сильно связный граф G=&lt;V,E&gt;, дугам(ребрам) и вершинам которого приписаны неотрицательные целые веса. Граф задан матрицей весов дуг A,u,v...

Поиск всех циклов в неориентированном графе. - C++
На входе программа принимает номера вершин и вес ребра между ними. Например: 2 3 1 - между вершинами 2 и 3 есть ребро весом 1. Нужно...

Выведение всех возможных маршрутов в неориентированном графе - C++
Помогите пожалуйста составить программу для выведения всех возможных маршрутов в неориентированном графе

Как найти все циклы в неориентированном графе по ребрам? - C++
Как найти все циклы в неориентированном графе по ребрам?

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2016, 21:35
Привет! Вот еще темы с ответами:

не компилируется задание: компонент связности графа - кто разберется - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;stdlib.h&gt; class Stack { private: int stackSize; int* stackArray; ...

Методом обхода в глубину определить число компонент связности и цикломатическое число графа - C++
Методом обхода в глубину определить число компонент связности и цикломатическое число графа – минимальное число ребер, которые надо...

Посчитать количество всех букв и количество вхождений каждой буквы - C++
Есть файл из нескольких строк. нужно: 1 посчитать количество всех букв 2 посчитать количество каждой из букв (abcd) Проблема:...

Посчитать количество четных и количество нечетных членов массива - C++
Здравствуйте! Прошу помочь в создании одномерного динамического массива с целыми числами. Посчитать кол-во четных и кол-во нечетных. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru