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

динамическое программирование - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ анимация в С++ http://www.cyberforum.ru/cpp-beginners/thread360134.html
как заставить шарик вращаться?
C++ Функция гипотенуза Выдаёт значения но какие то не правильные например если ввести 2 и 2 то должно быть 8, а выдаёт 84 Что не так ? #include "stdafx.h" #include<iostream> #include <math.h> #include<cmath> using... http://www.cyberforum.ru/cpp-beginners/thread360123.html
Просьба помочь реализовать класс. C++
Картка персони містить прізвище й дату народження. Реалізувати клас ListPerson для роботи з картотекою персоналій. Клас повинен містити масив карток персон. Реалізувати методи додавання й видалення...
C++ Задача на методы половинного деления
Ребята помогите пожалуйста внести в систему метода половинного деления вот эту функцию: 4(Sin^4)x+2(Cos^3)x+7=0 #include <conio.h> #include <math.h> #include <iostream.h> #define pi 3.14 double...
C++ case-switch http://www.cyberforum.ru/cpp-beginners/thread360107.html
Вот то задание что с case-switch надо сделать помогите знаю что задание дурное
C++ Поиск структур по условию Известны максимальные скорости 20 моделей легковых автомобилей. Марки моделей записаны в отдельном текстовом файле. Напечатать названия моделей, у которых максимальная скорость больше 180 км/ч. ... подробнее

Показать сообщение отдельно
x1Mike7x
217 / 130 / 6
Регистрация: 06.11.2010
Сообщений: 234
06.10.2011, 01:52
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
#include <iostream>
#include <vector>
 
std::vector < std::vector < int > > G; // Наш граф, для каждой вершины сохраняем список вершин, куда можно добраться за один шаг ( т.е. для каждого первака список его непосредственных друзей )
std::vector < bool > used; // Массив, где отмечаем или мы отметили вершину ( первака ) как просмотренного ( т.е. что у него есть друзья в некотором кругу )
 
void dfs( int V ) // функция поиска в глубину, параметр - номер вершины, которую просматриваем
{
        used.at( V ) = true; // Отмечаем, что мы были в вершине
        for ( unsigned i = 0, S = G.at( V ).size(); i < S; ++i ) // Идём по списку вершин для вершины V
                if ( !( used.at( G.at( V ).at( i ) ) ) ) // Если мы не были в і-ой вершине из списка
                        dfs( G.at( V ).at( i ) ); // то вызываем рекурсивно этот поиск в глубину для і-ой вершины
}
 
int main()
{
        int N, K, A, B;
        bool X = true; /// Переменная, которая будет показывать, или все вершины находятся в 1й компоненте связности, или нет
        
        std::cin >> N >> K;
        
        G.resize( N ); // Задаём, что у нас N вершин-перваков ( и следовательно столько будет списков непосредственных друзей )
        used.resize( N );
        used.assign( N, false ); // Весь массив used заполняем как будто мы не были ни в одной вершине
        
        while ( K-- )
        {
                std::cin >> A >> B; // Читаем связки друзей
                --A; --B; // Учитываем индексацию с 0, а не с 1;
                G.at( A ).push_back( B ); // Добавляем в список нового друга первака А
                G.at( B ).push_back( A ); // Добавляем в список нового друга первака В
        }  
        
        // Вызов функции поиска. Нам всё равно из какой вершины его вызывать, потому что нам нужно проверить всего-лишь или компонент связности больше 1
        dfs( 0 );
        
        // В цикле перебираем массив used, используем побитовое умножение - если хотя бы раз встретится в массиве значение false, то Х станет тоже false и цикл прекратится.
        for ( unsigned i = 0, S = used.size(); i < S && X; ++i )
                X &= used.at( i );
 
        // На основе Х выводим ответ - если Х так и остался true, то выводим "Да", иначе выводим "Нет"               
        std::cout << ( X ? "Yes" : "No" ) << std::endl;
                
        return 0;
}
Почитать про графы ( да и не только ) можно вот здесь: http://e-maxx.ru/algo/
Для конкретно этой задачи темы "Поиск в глубину" и "Поиск компонент связности" ( правда здесь, в задаче, нужны лишь знания, что это такое, т.к. решение сводится просто к поиску в глубину ).
4
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru