|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
02.10.2009, 21:56 | #1 |
Регистрация: 02.10.2009
Сообщений: 3
|
Графы на С++
Помогите плиз!
Есть задача: Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует принцип:"Знакомые моих знакомых - мои знакомые" Задача найти пары студентов которых надо познакомить для того чтобы все студенты знали друг дрга... По идее реализуется через Граф,вот только у меня не получается граф на С++ построить..... Помогите кто может... |
02.10.2009, 23:32 | #2 |
C++ hater
СтарожилДжуниор
Регистрация: 19.07.2009
Сообщений: 3,333
|
ну могу предложить полный перебор. Проверяешь каждую вершину на достижимость с каждой другой, например, поиском в глубину. Если вершины не достижимы - этих людей надо познакомить. Ну это что сразу приходит в голову
а вообще мне кажется тут все крутится на минимальном остовном дереве, но это его заюзать - пока не понял
I invented the term Object-Oriented, and I can tell you I did not have C++ in mind. (c)Alan Kay
My other car is cdr. Q: Whats the object-oriented way to become wealthy? A: Inheritance |
02.10.2009, 23:50 | #3 |
C++ hater
СтарожилДжуниор
Регистрация: 19.07.2009
Сообщений: 3,333
|
а, вот еще вариант. разбиваешь граф на сильно связанные компоненты, и соединяешь их. точки соединения будут студентами, которых надо познакомить. одинокого студента тоже считать сильно связанной компонентой, для простоты.
пример: маша знает витю и васю. вася знает колю и олю. игорь знает петю. костя (это я) не знает никого. имеем 3 сильно связанные компоненты: 1. маша витя вася коля оля 2. игорь петя 3. костя тут уж кого с кем знакомить я думаю без разницы. познакомишь олю с игорем, а петю с костей и все будут друг друга знать. наверное так.
I invented the term Object-Oriented, and I can tell you I did not have C++ in mind. (c)Alan Kay
My other car is cdr. Q: Whats the object-oriented way to become wealthy? A: Inheritance Последний раз редактировалось pproger; 02.10.2009 в 23:52. |
03.10.2009, 01:42 | #4 |
Форумчанин
Регистрация: 02.06.2009
Сообщений: 218
|
я еще хочу напомнить что тут может и поиграть роль - точки сочленения ))) ну эт наверное, просто я делал курсовую, нахождение двусвязных компонент )))
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Графы | Prisian | Общие вопросы Delphi | 11 | 02.05.2013 22:02 |
графы на Delphi | UMmi | Общие вопросы Delphi | 12 | 26.02.2011 14:14 |
графы | paladinn | Помощь студентам | 1 | 07.06.2009 18:04 |
Графы в Delphi | Ира08 | Помощь студентам | 0 | 21.04.2009 21:46 |
Задача (на графы) | Witaliy | Помощь студентам | 6 | 14.02.2009 17:47 |