Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
sven_mp
0 / 0 / 0
Регистрация: 08.04.2016
Сообщений: 12
#1

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

18.04.2016, 21:35. Просмотров 125. Ответов 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
Ответы с готовыми решениями:

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

Нужно немного переделать программу нахождения компонент сильной связности в графе
В общем задание такое, нужно переделать эту программу, я не знаю как это...

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

Поиск всех циклов в неориентированном графе.
На входе программа принимает номера вершин и вес ребра между ними. Например:...

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

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

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

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

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


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

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

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