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

Эйлеров путь - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Рекурсия в цикле http://www.cyberforum.ru/cpp-beginners/thread1036565.html
Помогите пожалуйста, срочно нужно с этим разобраться. Как она работает? Правильно составлена последовательность вызовов?
C++ Что такое паралельные потоки? Что такое паралельные потоки? http://www.cyberforum.ru/cpp-beginners/thread1036549.html
Извлечение из списка всех нулевых елементов C++
С++ Не могу никак разобраться что делаю не так. Суть заключаеться - ввожу любые елементы например 5, 10, 0 ,3, 4, 0, 8 или любые а в результате списка должен получиться числа без нулей тоесть 5, 10, 3, 4, 8. Я уже запутался что к чему, прошу вашей помощи.#pragma agrused #include <iostream.h> #include <stdlib.h> #include <conio.h> // shablon vuzliv spusky typedef struct node {node *next;...
Матрицы. Расположить элементы строк в порядке возрастания C++
помогите пожалуйста нужно вывести исходную матрицу с файла на экран, расположить элементы строк в порядке возрастания и тоже вывести на экран -2 1 3 -1 4 8 0 5 -8 7 6 -3 5 3 14 0 4 1 -15 12 0 -9 -8 4
C++ Написать функцию для приближенного вычисления log http://www.cyberforum.ru/cpp-beginners/thread1036536.html
Написать функцию для приближенного вычисления log2x с помощью многочлена наилучшего приближения: {log}_{2}x \approx \sum_{k=1}^{3} {a}_{2k-1} {(\frac{x-1}{x+1})}^{2k-1} , где: 1<=x<=2^0.5 a1 = 2.8854; a3 = 0.9615; a5 = 0.959
C++ Написать программу вывода на экран значений функции помогите,пожалуйста подробнее

Показать сообщение отдельно
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 09:47     Эйлеров путь
Цитата Сообщение от Aliru Посмотреть сообщение
28(иногда меньше, иногда больше) минут
жесть!
сие творение ищет эйлеров путь за N*logN (можно избавиться от логарифма если set заменить на что-нибудь на хешах, например unordered_map):
C++
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <set>
#include <stack>
using namespace std;
 
const int N = 10001;
 
set< int > adj[ N ]; // граф на списках смежности
stack< int > st;
 
void insert_edge( int v, int w )
{
    adj[ v ].insert( w );
    adj[ w ].insert( v );
}
 
void remove_edge( int v, int w )
{
    adj[ v ].erase( w );
    adj[ w ].erase( v );
}
 
int traverse( int v )
{
    for ( set< int >::iterator it; ( it = adj[ v ].begin() ) != adj[ v ].end(); v = *it )
    {
        st.push( v );
        remove_edge( v, *it );
    }
    return v;
}
 
void print_euler( int v )
{
    st.push( v = traverse( v ) );
    while ( !st.empty() )
    {
        printf( "%d ", v = st.top() ); st.pop();
        traverse( v );
    }
}
 
int find_odd_degree()
{
    for ( int v = 0; v < N; ++v )
        if ( adj[ v ].size() & 0x01 )
            return v;
    return -1;
}
 
int main()
{
    for ( int v, w; 1 < scanf( "%d%d", &v, &w ); insert_edge( v, w ) );
    print_euler( find_odd_degree() );
 
    return 0;
}
 
Текущее время: 05:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru