CSES - (Negative) Cycle Finding

Problem Link (Click here)

Tags: Directed Graph, Bellman Ford

The problem statement is quite clear: find a negative cycle in a directed graph.

Use the Bellman-Ford algorithm.

In this problem, the goal is not to find the shortest path from one node to all others, so there is no need to set the distance of the starting node to 0 (as described in the original algorithm). Instead, set the initial distances of all nodes to the same value (I have set them all to 0 for sake of simplicity).

Run the Bellman-Ford algorithm for n rounds, and whenever a distance gets reduced, keep track of the node's predecessor. In the nth round, if a node gets reduced, then the graph contains a negative cycle. Otherwise, the graph does not contain a negative cycle. Record the last node which gets reduced.

To guarantee that a node which is part of the negative cycle is found, find the predecessor of the last node visited, n times.

This works because by backtracking n times, we will visit all nodes and eventually visit a node which is part of the negative cycle. 

Once a node in the negative cycle is found, backtrack once more until the original node you started with is found. These nodes form a negative cycle.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2501;

vector <tuple<int, int, int>> edges;

int parent[MAX_N];

int main()

{

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; i++){

        int a, b, w;

        cin >> a >> b >> w;

        edges.push_back({a, b, w});

    }

    vector <long long> dis(n+1, 0);

    int last_node_visited = -1;

    for (int round = 1; round <= n; round++){

        for (auto i : edges){

            int a, b, w;

            tie(a, b, w) = i;

            if (dis[b] > dis[a]+w){

                dis[b] = dis[a]+w;

                parent[b] = a;

                last_node_visited = b;

            }

        }

    }

    if (last_node_visited == -1){

        cout << "NO\n";

        return 0;

    }

    cout << "YES\n";

    vector <int> ans;

    for (int i = 0; i < n; i++)

        last_node_visited = parent[last_node_visited];

    for (int node = last_node_visited; ; node = parent[node]){

        ans.push_back(node);

        if (ans.size() > 1 && node == last_node_visited)

            break;

    }

    reverse(begin(ans), end(ans));

    for (auto i : ans)

        cout << i << ' ';

}