|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
14.02.2009, 15:49 | #1 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
Задача (на графы)
Всем привет
Возникла такая задача: В классе Петрика все дети очень дружные. Среди учеников этого класса выполняется такое правило - друг моего друга мой друг. Также, если Петрик дружит с Андрейком, то Андрейко не обязательно дружит с Петриком. Учительница знает, что некоторые дети дружат, но обо всех она не знает. Все же учительнице хочется узнать, насколько у нее дружеский класс. Для этого Вам нужно определить, сколько существует упорядоченных пар друзей в этом классе (ученики сами с собой не дружат). 1<=N<=500 1<=N<=5000 Вход. Диние: N-количество учеников в классе, M - количество пар, о которых учительнийца знает, что они дружат. В следующий М рядках указаны ети пары. Все ученики пронумерованние от 1 до N Вых. Дание: Количество дружных пар учеников. Например 2 3 1 2 2 3 Результат: 3 Тепер моя точка зрения для примера: количество пар всегда будет больше за N. Для примера будут такие варианты: (1,2) (2,3) и (1,3), бо 3 друг друга 1 Как я понял, задачю надо решать на графы, но не знаю как. Благадарен за любую помошь. Спасибо. (за русский извините, я ученик с Украины)
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
14.02.2009, 16:32 | #2 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Сразу оговорюсь, что с графами знаком плохо.
Вроде работает. Код:
Код:
И на Код:
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] Последний раз редактировалось Sazary; 14.02.2009 в 16:52. Причина: удалил лишнюю строчку |
14.02.2009, 16:36 | #3 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
Очень большое спасибо, а как назыветься такой алгоритм?
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
14.02.2009, 16:42 | #4 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
Извините, моя ошыбка:
Например 3 2 1 2 2 3
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
14.02.2009, 16:47 | #5 | ||
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Цитата:
Цитата:
Далее идут M строк (пары, о которых известно) То, что вы сейчас привели, под эти критерии не подходит ) ---- Если нужно, могу описать логику работы (вроде как, там и так все понятно, но, может быть, это только для меня ))
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] Последний раз редактировалось Sazary; 14.02.2009 в 16:51. |
||
14.02.2009, 17:22 | #6 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
было б хорошо.
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
14.02.2009, 17:47 | #7 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Сначала читаем M (количество известных пар) и N (количество учеников).
Код:
Код:
Код:
Код:
Код:
ti - ученик, для которого мы ищем друзей (по принципу "друг моего друга - мой друг"). ci - текущий друг в цепочке. Процедура: Запускаем цикл, который обходит всех учеников: Код:
Код:
Код:
Если текущий (в этом цикле) ученик дружит с текущим (из вне) другом исходного ученика: Код:
Код:
Код:
Код:
Когда обошли всех и вся, возвращаемся в программу. Там уже обходим всех учеников и по матрице смежности смотрим кто с кем дружит (и плюсуем cnt): Код:
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] Последний раз редактировалось Sazary; 14.02.2009 в 18:10. Причина: опечатка |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Графы | Prisian | Общие вопросы Delphi | 11 | 02.05.2013 22:02 |
графы на Delphi | UMmi | Общие вопросы Delphi | 12 | 26.02.2011 14:14 |
Графы, матрица смежности. | SteRN89 | Помощь студентам | 1 | 14.01.2009 08:11 |