In C++

gistfile1.txt

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

void dfs(int node, vector<int>& edges, vector<bool>& visited, vector<int>& stack, int path_sum, unordered_map<int, int>& node_to_sum, int& max_cycle_sum) {
    visited[node] = true;
    stack[node] = path_sum;
    node_to_sum[node] = path_sum;
    
    int next_node = edges[node];
    if (next_node != -1) {
        if (!visited[next_node]) {
            dfs(next_node, edges, visited, stack, path_sum + next_node, node_to_sum, max_cycle_sum);
        } else if (stack[next_node] != -1) {
            // Cycle detected
            int cycle_sum = path_sum - node_to_sum[next_node] + next_node;
            max_cycle_sum = max(max_cycle_sum, cycle_sum);
        }
    }
    
    stack[node] = -1;  // Remove the node from the current path
}

int find_largest_sum_cycle(int n, vector<int>& edges) {
    vector<bool> visited(n, false);
    vector<int> stack(n, -1);  // Keeps track of the nodes in the current path
    unordered_map<int, int> node_to_sum;
    int max_cycle_sum = -1;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, edges, visited, stack, i, node_to_sum, max_cycle_sum);
        }
    }

    return max_cycle_sum;
}

int main() {
    int n = 23;
    vector<int> edges = {4, 4, 14, 13, 8, 8, 0, 8, 14, 9, 15, 11, -1, 10, 15, 22, 22, 22, 22, 22, 21};

    int result = find_largest_sum_cycle(n, edges);
    cout << result << endl;  // Output: 45

    return 0;
}