Cycle Finding

You are given a directed graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.

Example:

Input:  n = 4, m = 5, e = {{1, 2, 1}, {2, 4, 1}, {3, 1, 1}, {4, 1, -3}, {4, 3, -2}}

Output:

YES
4 1 2 4

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1LL << 62;

void cycleFinding(int n, int m,
                  vector<tuple<int, int, int>> &e)
{

    //using bellman-ford algorithm
    long long dis[n + 1], par[n + 1] = {0};
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    int f;
    for (int i = 1; i <= n; i++)
    {
        f = 0;

        for (auto [a, b, w] : e)
        {

            //relaxation
            if (dis[a] + w < dis[b])
            {
                //update distance
                dis[b] = dis[a] + w;

                //update parent
                par[b] = a;
                f = b;
            }
        }
    }
    if (!f)
    {
        cout << "NO\n";
        return;
    }
    else
    {
        cout << "YES\n";
        vector<int> cyc;
        for (int i = 1; i <= n; i++)
            f = par[f];
        for (int x = f;; x = par[x])
        {
            cyc.push_back(x);
            if (x == f && cyc.size() > 1)
                break;
        }
        for (int i = cyc.size() - 1; i >= 0; i--)
            cout << cyc[i] << " ";
    }
}
int main()
{
    int n = 4, m = 5;

    vector<tuple<int, int, int>> e = {{1, 2, 1},
                                      {2, 4, 1},
                                      {3, 1, 1},
                                      {4, 1, -3},
                                      {4, 3, -2}};

    cycleFinding(n, m, e);

    return 0;
}