Графы на С++ - Общие вопросы C/C++

corri · 02.10.2009, 21:56

Помогите плиз!
Есть задача:
Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует принцип:"Знакомые моих знакомых - мои знакомые" Задача найти пары студентов которых надо познакомить для того чтобы все студенты знали друг дрга...
По идее реализуется через Граф,вот только у меня не получается граф на С++ построить.....
Помогите кто может...

pproger · 02.10.2009, 23:32

ну могу предложить полный перебор. Проверяешь каждую вершину на достижимость с каждой другой, например, поиском в глубину. Если вершины не достижимы - этих людей надо познакомить. Ну это что сразу приходит в голову

а вообще мне кажется тут все крутится на минимальном остовном дереве, но это его заюзать - пока не понял

pproger · 02.10.2009, 23:50

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

пример:
маша знает витю и васю.
вася знает колю и олю.
игорь знает петю.
костя (это я) не знает никого.

имеем 3 сильно связанные компоненты:
1. маша витя вася коля оля
2. игорь петя
3. костя

тут уж кого с кем знакомить я думаю без разницы. познакомишь олю с игорем, а петю с костей и все будут друг друга знать.
наверное так.

Olejik · 03.10.2009, 01:42

я еще хочу напомнить что тут может и поиграть роль - точки сочленения ))) ну эт наверное, просто я делал курсовую, нахождение двусвязных компонент )))

02.10.2009, 21:56	#1
corri Регистрация: 02.10.2009 Сообщений: 3	Графы на С++ Помогите плиз! Есть задача: Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует принцип:"Знакомые моих знакомых - мои знакомые" Задача найти пары студентов которых надо познакомить для того чтобы все студенты знали друг дрга... По идее реализуется через Граф,вот только у меня не получается граф на С++ построить..... Помогите кто может...

02.10.2009, 23:32	#2
pproger 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
pproger 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.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Графы	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

03.10.2009, 01:42	#4
Olejik Форумчанин Регистрация: 02.06.2009 Сообщений: 218	я еще хочу напомнить что тут может и поиграть роль - точки сочленения ))) ну эт наверное, просто я делал курсовую, нахождение двусвязных компонент )))