Помогите с графами!!! - Форум
Понедельник, 05.12.2016, 07:24
Задачи по информатике
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: ignorer, KOT_B_MEIIIKE, PASCAL26, atvrider 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » Помогите с графами!!!
Помогите с графами!!!
Julia_kovaДата: Вторник, 08.11.2011, 08:53 | Сообщение # 1
Сержант
Группа: Новичок
Сообщений: 5
[ 0 ]
Статус: Offline
В некоторой стране существуют несколько авиакомпаний. Причем, любой рейс любой авиакомпании соединяет города, которые не соединяет ни один из рейсов любой другой авиакомпании. Каждый рейс соединяет только два города. Один и тот же город может быть начальным или конечным пунктом многих рейсов одной авиакомпании.
Определите по заданному списку рейсов количество авиакомпаний.
Входные данные:
На первой строкечисла Nи M, разделенные пробелом; где N – количество городов в стране, 2<=N<=10000, M–количество авиарейсов, 1<=M<=500000.
В следующих Mстроках записаны по два числа – номера городов, которые соединяет очередной рейс.
Выходные данные:
Одно число – количество рейсов.
Пример
Input.txt Output.txt
75
1 3
5 7
6 3
2 4
3 5 2
 
PASCAL26Дата: Вторник, 08.11.2011, 16:13 | Сообщение # 2
Генералиссимус
Группа: Модераторы
Сообщений: 215
[ 23 ]
Статус: Offline
задача на раскраску графа? поищи алгоритм тут http://e-maxx.ru/algo/, а так думаю что к четвергу написать смогу, раньше никак

пишу на с++, delphi, c# (нудные задачи небезвозмедно)
ps Если помог - щелкни +, и вам хорошо и мне приятно
 
Julia_kovaДата: Среда, 09.11.2011, 06:55 | Сообщение # 3
Сержант
Группа: Новичок
Сообщений: 5
[ 0 ]
Статус: Offline
Спасибо.. если можно, попробуйте ее реализовать..

Та ссылка - пишет, что алгоритм не найден..
Знаю, что нужно граф обходить в ширину или в глубину, затем считать колличество совпадений смежных вершин и тд.. но никак не могу реализовать..(


Сообщение отредактировал Julia_kova - Среда, 09.11.2011, 07:44
 
KOT_B_MEIIIKEДата: Среда, 09.11.2011, 09:47 | Сообщение # 4
Генералиссимус
Группа: Модераторы
Сообщений: 284
[ 36 ]
Статус: Offline
PASCAL26, ты теперь олимпиады решать стал?
 
PASCAL26Дата: Пятница, 11.11.2011, 20:22 | Сообщение # 5
Генералиссимус
Группа: Модераторы
Сообщений: 215
[ 23 ]
Статус: Offline
это не олимпиадка а скорее тренировка(я почти уверен что олимпиада бы уже закончилась) - плюс мне тренировка, тк сам участвую во многих.
P.s. да и к тому же это первая действительно интересная задача на форуме


пишу на с++, delphi, c# (нудные задачи небезвозмедно)
ps Если помог - щелкни +, и вам хорошо и мне приятно


Сообщение отредактировал PASCAL26 - Пятница, 11.11.2011, 20:27
 
PASCAL26Дата: Пятница, 11.11.2011, 20:49 | Сообщение # 6
Генералиссимус
Группа: Модераторы
Сообщений: 215
[ 23 ]
Статус: Offline
так ну вод основной код вроде
если будет ошибка компиляции посмотри может там еще чего подключить надо, ну думаю без дебага она врятли пройдет взят алгоритм отсюда(http://e-maxx.ru/algo/tree_painting)
Прикрепления: 7093055.txt(4Kb)


пишу на с++, delphi, c# (нудные задачи небезвозмедно)
ps Если помог - щелкни +, и вам хорошо и мне приятно
 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » Помогите с графами!!!
Страница 1 из 11
Поиск:

Copyright MyCorp © 2016