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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти минимальное количество пересадок между двумя городами http://www.cyberforum.ru/cpp-beginners/thread853886.html
Здраствуйте!Помогите пожалуйста Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти минимальное количество пересадок между двумя городами. Гарантируется,...
C++ Определить количество пар, которое может образоваться, и укажите эти пары (задача "Охота") На охоту поехали n человек. Половина из них не имели патронов. Охотники разделились на два равные группы: первая группа с патронами, вторая – без патронов. Первая группа решила курировать над второй... http://www.cyberforum.ru/cpp-beginners/thread853883.html
обращение к подструктурам и их функциям C++
Ребята написал программу, вот подскажите как мне обратится к подструктурам и их функциям. Просто мне нужно получить их значения. Или я что-то не правильно понял и так делать нельзя? #include...
C++ Подгружаемая библиотека
Подскажите пожалуйста ибо сам зашел в тупик. Есть программа, которая заражает конкретный процесс. Т.е заражаем процесс перехватываем функции CreatFileA(W), OpenFile и др.(при вызове этих функций...
C++ Анаграммы http://www.cyberforum.ru/cpp-beginners/thread853866.html
Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).
C++ static указатель на метод (LNK2001) Имеется класс A, один из его методов B(int a) нужно указать напрямую (по адресу). Делал так: #include "windows.h" class A { public: static void (__thiscall* B)( int a); }; void... подробнее

Показать сообщение отдельно
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
30.05.2013, 12:08
решение через Disjoint Union-Set:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}
Программа не дописана. Я оставил немного работы для тебя (см. комментарий в программе). Разберешься с дисджоинтом и сам поймешь что надо дописать.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru