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

Найти цикл в графе - C++

Восстановить пароль Регистрация
 
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
25.11.2011, 19:56     Найти цикл в графе #1
Дан граф, содержащий только один цикл. Нужно найти его (все его вершины).
Код не нужен, нужна только идея.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2011, 19:56     Найти цикл в графе
Посмотрите здесь:

Гамильтонов цикл в графе C++
C++ Гамильтонов цикл в графе с выполненным условием Дирака
найти одинаковые элементы в массиве/Цикл C++
C++ Цикл с while: найти простые числа в промежутке [a, b]
Найти все пути между двумя любыми вершинами в графе C++
Найти вероятность существования пути в графе между заданными точками C++
Цикл For: найти ошибку в коде C++
C++ Как найти НЕ Кратчайший путь в графе ?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
25.11.2011, 20:28     Найти цикл в графе #2
прямолинейный способ, то рекурсивно обходим весь граф, по пути записывая маршрут
если вершина уже встречалась по пути - цикл

вот даже у себя быдлокод на эту тему откопал
http://liveworkspace.org/code/74657c...5089f30044f8a4
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
25.11.2011, 20:40  [ТС]     Найти цикл в графе #3
alex_x_x, проблема в том, как его вывести. Полчаса уже туплю над массивом предков...

Добавлено через 28 секунд
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
 
using namespace std;
 
vector < vector <int> > g;
int n, go[3000], ctop;
bitset <3000> used;
 
int dfs (int v)
{
    if (ctop != -1)
        return ctop;
 
    used[v] = true;
 
    for (int i = 0; i < g[v].size(); i++)
    {
        if (go[g[v][i]] == v)
            continue;
 
        go[v] = g[v][i];
 
        if (used[g[v][i]])
        {
            ctop = g[v][i];
            return g[v][i];
        }
        else
            dfs(g[v][i]);
    }
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int i, j, a, b;
    set <int> cycle;
 
    cin >> n;
 
    g.resize(n);
 
    for (i = 0; i < n; i++)
    {
        cin >> a >> b;
 
        a--; b--;
 
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    ctop = -1;
    memset(go, -1, 3000);
    ctop = dfs(0);
 
    cycle.insert(ctop);
 
    i = go[ctop];
 
    while (i != ctop)
    {
        cycle.insert(i);
        i = go[i];
    }
 
    for (set<int>::iterator it = cycle.begin(); it != cycle.end(); it++)
        cout << *it << ' ';
 
    return 0;
}
Будет работать?
Yandex
Объявления
25.11.2011, 20:40     Найти цикл в графе
Ответ Создать тему
Опции темы

Текущее время: 10:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru