Форум программистов, компьютерный форум CyberForum.ru

Достроение до сильно связного орграфа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ g++/gcc не компилирует http://www.cyberforum.ru/cpp-beginners/thread826891.html
есть С++ код #include <iostream> int main(){ std::cout << "hello ,world!"; } запускаю компилятор и он ничего не делает ,совсем. запускаю компилятор батником:
C++ Дан текст, состоящий не менее чем из пяти слов. Сформировать стек из тех слов, в которых присутствует буква "Е" Дан текст, состоящий не менее чем из пяти слов. Сформировать стек из тех слов, в которых присутствует буква "Е". Помогите пожалуйста решить задачу) Ничего на ум не приходит( http://www.cyberforum.ru/cpp-beginners/thread826890.html
C++ Программа не всегда работает правильно
Всем добрый вечер. Реализовал программу, подсчитывающую корень уравнения методом касательных(Ньютона). В качестве примера использовал трансцендентное уравнение вида: f(x)=e^x*(ax^3+(a)*x^2-(a)). на на последнем скрине подсчет не верен. Подскажите пожалуйста как исправить? и еще вопрос менее важен. При нажатии на кнопку 1 происходит подсчет программы. На кнопку 2 выход. При нажатии на другую...
C++ Область комнаты (рекурсия)
Здраствуйте. помогите решить задачу площадь комнаты Ваша задача написать программу, которая найдет площадь комнаты в данном квадратный лабиринт Ввод: Первая строка содержит только одно число N (3 <= N <= 10). Число, которое описывает размер площади лабиринта. На следующих строках мы вводим сами ('.' - Пустые ячейки, '*' - стены). И последняя строка содержит два числа - строки и столбца...
C++ Адрес объекта, адрес указателя. Где что находится? http://www.cyberforum.ru/cpp-beginners/thread826862.html
#include <iostream> void Foo(int* val) { std::cout << val << " " << *val << " " << &val << '\n'; } void Bar(int* &val) { std::cout << val << " " << *val << " " << &val << '\n';
C++ Задача на подсчет и вычисление в одномерном массиве с++ Ребята помогите с заданием по с++: "Подсчитать количество простых чисел в одномерном массиве, которые больше своих соседних элементов справа и слева. В этом же массиве найти сумму таких элементов, которые больше всех предшествующих им элементов (массив любой)" подробнее

Показать сообщение отдельно
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
05.04.2013, 18:49     Достроение до сильно связного орграфа
Цитата Сообщение от Ternsip Посмотреть сообщение
не понял главного -- какие именно дуги ставить
По второй ссылке написано какие именно дуги нужно добавлять в DAG, чтобы получить из него сильно связную компоненту:
Assuming there are no isolated vertices in the graph you only need to add max(|sources|,|sinks|) edges to make it strongly connected.

Let T={t1,…,tn} be the sinks and {s1,…,sm} be the sources of the DAG. Assume that n <= m. (The other case is very similar). Consider a bipartite graph G(T,S) between the two sets defined as follows. G(T,S) has an edge (ti,sj) if and only if ti can be reached from sj.

Let M be a maximal matching in G(T,S). Without loss of generality assume that M consists of k edges: {(t1,s1),(t2,s2),…,(tk,sk)}. In the original graph DAG G, add directed-edges {(t1->s2),(t2->s3),…,(tk−1->sk),(tk->s1)}. It's easy to see that by adding these edges, the vertices induced by M are strongly connected in G.

Now consider the remaining vertices in G(T,S). Because M maximal, each vertex in S−M (resp. T−M)should be connected to a vertex in T (resp. S−M). So we pair up the remaining vertices arbitrarily, say {(tk+1,sk+1),…,(tn,sn)} and add the corresponding directed edges in G. For each remaining source vertex source si (i belongs to {n+1,…,m} we add the edge (t1->si) in G. Thus the total number of edges added is max(|sources|,|sinks|).
 
Текущее время: 18:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru