Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.423 RSS
←   Июнь 2012   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.423 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Советник
Рейтинг: 10955
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4338
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2495
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1760
Дата выхода:18.06.2012, 14:00
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:130 / 91
Вопросов / ответов:1 / 1

Консультация # 186373: Здравствуйте! Прошу помощи в следующем вопросе: В курсовой работе по дискретной математике присутствует такое задание: 1.Изучить алгоритм 2.Составить программу алгоритма 3.Отладить тестовые примеры 4.Провести оценку сложности алгоритма 5.Составить прикладную задачу, для решения которой используется данный алгоритм

Консультация # 186373:

Здравствуйте! Прошу помощи в следующем вопросе:

В курсовой работе по дискретной математике присутствует такое задание:

1.Изучить алгоритм
2.Составить программу алгоритма
3.Отладить тестовые примеры
4.Провести оценку сложности алгоритма
5.Составить прикладную задачу, для решения которой используется данный алгоритм

Алгоритм "Нахождение компонент сильной связности графа"

Я не умею писать программы, но задание нужно сдать.Очень прошу помощи у экспертов портала, помогите, пожалуйста, написать программу к этому алгоритму!( на языке Си )

Преподаватель не требовательный, в программировании не разбирается, проверяет только работоспособность программы.

Дата отправки: 15.06.2012, 13:30
Вопрос задал: Григорий Сальнечников (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Асмик Гаряка (Советник):

Здравствуйте, Григорий Сальнечников!

Описываемый здесь алгоритм был предложен независимо Косараю (Kosaraju) и Шариром (Sharir) в 1979 г. Это очень простой в реализации алгоритм, основанный на двух сериях поисков в глубину, и потому работающий за время O(n+m).

На первом шаге алгоритма выполняется серия обходов в глубину, посещающая весь граф. Для этого мы проходимся по всем вершинам графа и из каждой ещё не посещённой вершины вызываем обход в глубину. При этом для каждой вершины v запомним время выхода tout[v]. Эти времена выхода играют ключевую роль в алгоритме, и эта роль выражена в приведённой ниже теореме.
Определения

Ориентированный ациклический граф (directed acyclic graph) — это орграф, не содержащий направленных циклов.
Алгоритм
1. Инвертируем ребра исходного орграфа.
2. Запускаем поиск в глубину на этом обращенном графе. В результате получаем вектор обхода.
3. Запускаем поиск в глубину на исходном графе, в очередной раз выбирая непосещенную вершину с максимальным номером в векторе, полученном в п.2.
4. Полученные деревья из п.3, и являются сильно связными компонентами.

Код :
// 186373.cpp : Defines the entry point for the console application.

#include <vector>
#include <iostream>
using namespace std;

vector < vector<int> > g, gr; //g - graf gr transponirovanny graf
vector<char> used;  //pometki vershin
vector<int> order, component;
 
void dfs1 (int v) {
	used[v] = true;
	int n=g[v].size();
	for (size_t i=0; i<n; ++i)
		if (!used[ g[v][i] ])
			dfs1 (g[v][i]);
	order.push_back (v);
}
 
void dfs2 (int v) {
	used[v] = true;
	component.push_back (v);
	for (size_t i=0; i<gr[v].size(); ++i)
		if (!used[ gr[v][i] ])
			dfs2 (gr[v][i]);
}
 
int main() {
	int n;

	//... чтение n ...
	cout<<"vvedite kolichestvo vershin"<<endl;
	cin >>n;
	g.resize(n);
	gr.resize(n);
	for (;;) {
		int a, b;
	//	... чтение очередного ребра (a,b) ...
		cout<<"vvedite rebro"<<endl;
		cin >>a;
		if (a==0) break;
		cin >>b;
		g[a-1].push_back (b-1);
		gr[b-1].push_back (a-1);
	}
 
	used.assign (n, false);
	for (int i=0; i<n; ++i)
		if (!used[i])
			dfs1 (i);
	used.assign (n, false);
	for (int i=0; i<n; ++i) {
		int v = order[n-1-i];
		if (!used[v]) {
			dfs2 (v);
//			... вывод очередной component ...
			cout << "componenta silnoy svyaznosti"<< endl;
			for (int k=0; k<component.size(); ++k) {
			cout << component[k]+1;
			}
			cout << endl;
			component.clear();
		}
	}

}

Консультировал: Асмик Гаряка (Советник)
Дата отправки: 16.06.2012, 14:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное