Форум программистов, компьютерный форум, киберфорум
Наши страницы

Достроение до сильно связного орграфа - 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))....
C++ Область комнаты (рекурсия)
Здраствуйте. помогите решить задачу площадь комнаты Ваша задача написать программу, которая найдет площадь комнаты в данном квадратный лабиринт Ввод: Первая строка содержит только одно число...
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
127 / 131 / 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|).
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru