Как найти цикл в ориентированном графе?

Question

[Айнур Низамов]

Помогите, пожалуйста. Сам dfs и вообще все в этом роде знаю, но выдает ошибку "cycle: идентификатор не найден". Как я понял, функцию из функции вызывать нельзя, но на моей памяти я это вроде как и делал.

P. S. Я понимаю, что мой код ужасен

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ifstream fin("cycle.in");
ofstream fout("cycle.out");

const ll inf = 1e18;
const ll mod = 1e9;

int parent[10002];
bool color[100002];
vector<int>ans;
vector<vector<int>>mas(100002);


int cycle(int index, int to) {
    while (index != to) {
        ans.push_back(index);
        index = parent[index];
    }
    ans.push_back(to);
    fout << "YES\n";
    for (int i = ans.size() - 1; i >= 0; i--) fout << ans[i] << " ";
    exit(0);
}
void dfs(int index, int p = -1) {
    color[index] = 1;
    parent[index] = p;
    for (int i = 0; i < mas[index].size(); i++) {
        if (color[mas[index][i]] == 1 && mas[index][i] != p) cycle(index, mas[index][i]);
        dfs(mas[index][i], index);
    }
}


int main() {
    int n, m, from, to;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) color[i] = 0;
    for (int i = 1; i <= m; i++) { fin >> from >> to; mas[from].push_back(to); }
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) {
            dfs(i);
        }
    }
    fout << "NO";
}

Comments

[Евгений Шатунов]

Nizamovoff , у тебя cycle не имеет предварительного объявления и определена после dfs.
Сделай предварительное объявление cycle перед объявлением dfs или вообще перенеси определение cycle перед dfs.

Поиск функции при трансляции делается только среди уже объявленных имен. А у тебя сейчас cycle не объявлена в момент трансляции dfs.

[Айнур Низамов]

Евгений Шатунов, спасибо большое.

Кстати, я забыл в cycle() сделать присвоение index = parent[index];

Answer 1

[Wataru]

Один момент меня смущает: зачем вы внутри DFS не вызываете cycle когда у вас есть ребро в p? Это цикл длины 2 - вполне нормальный цикл. Или по условию задачи такие надо исключить?

А главная ошибка - надо при выходе из dfs помечать вершину другим цветом - как обработанную (например, 2). Чтобы color == 1 только у вершин, которые в стеке. При этом в самом Dfs нужно рекурсивно вызываться только отвершин с color == 0.

Допустим, у вас в графе есть ребро 2->1 и все. Вы вызоветесь от вершины 1 в цикле в main, ничего не найдете. Потом вызоветесь от вершины 2, найдете ребро в уже обработанную вершину и среагируете на это, как на цикл. Хотя это не цикл.

Comments

[Айнур Низамов]

Честно сказать, не подумал над этим. Благо моему везению решение зашло