Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297

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

25.11.2011, 19:56. Показов 3094. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дан граф, содержащий только один цикл. Нужно найти его (все его вершины).
Код не нужен, нужна только идея.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.11.2011, 19:56
Ответы с готовыми решениями:

Найти эйлерову цепь или эйлеров цикл в графе
Найти эйлерову цепь или эйлеров цикл в графе

Гамильтонов цикл в графе
Нужно написать функцию нахождения гамильтонова цикла в графе. Цикл ищется по матрице смежности которая вводится с клавиатуры. Собственно...

Вернуть рёбра из которых состоит цикл в графе
допустим, есть граф, как на картинке. визуально и так видно, что там циклы, это: 1 2 3 4 5 и 6 7 8, но как реализовать, чтобы...

2
бжни
 Аватар для alex_x_x
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
25.11.2011, 20:28
прямолинейный способ, то рекурсивно обходим весь граф, по пути записывая маршрут
если вершина уже встречалась по пути - цикл

вот даже у себя быдлокод на эту тему откопал
http://liveworkspace.org/code/... f30044f8a4
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.11.2011, 20:40  [ТС]
Лучший ответ Сообщение было отмечено iama как решение

Решение

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;
}
Будет работать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
25.11.2011, 20:40
Помогаю со студенческими работами здесь

Гамильтонов цикл в графе с выполненным условием Дирака
:Задача 1 . SMS счастья Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 2 секунды на...

Определить есть ли во взвешенном графе цикл отрицательного веса
(Время: 1 сек. Память: 16 Мб Сложность: 46%) Дан взвешенный граф. Определить, есть ли в нем цикл отрицательного веса. Входные данные...

Найти цикл в графе
matr (1,2) = 1; matr (2,6) = 4; matr (6,4) = 1; matr (4,1) = 2; matr (5,4) = 2; matr (7,5) = 5; matr (7,3) = 4; matr (3,1) =...

Найти цикл в графе, содержащий заданные вершины.
в неориентированном графе для двух заданных вершин найти какой-нибудь цикл, на котором лежат эти вершины

Найти длину цикла в полном графе с n вершинами, цикл содержит хотя бы один раз каждое ребро
формулу или объяснить на примере


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&amp;d=1772460536 Одним из. . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru