# Untitled

unknown
c_cpp
a month ago
1.4 kB
2
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX

long long largestSumCycle(int n, vector<int> edge)
{

// cnt vector will count the Indegree of each Node
vector<int> cnt(n,0);

for(auto i : edge){
if(i != -1) cnt[i]++;
}

queue<int> q;

/*

Fact that a Node with indegree = 0 is out of cycle.
We'll mark that node visited and cut that node from the graph.
To do so, find the edge from that node and decrease the indegree of edge[node] by 1.

*/

vector<int> vis(n,0);
for(int i = 0; i<n; i++){
if(cnt[i]==0){
vis[i] = 1;
q.push(i);
}
}

while(!q.empty()){
int node = q.front(); q.pop();
if(edge[node] == -1) continue;
--cnt[edge[node]];
if(cnt[edge[node]] == 0){
vis[edge[node]] = 1;
q.push(edge[node]);
}
}

int ans = -1;

for(int i = 0; i<n; i++){
if(vis[i]) continue;
int val = 0;
for(int st = i; vis[st] == 0; st = edge[st]){
vis[st] = 1;
val += st;
}
ans = max(ans,val);
}

return ans;

}

int main()
{
int n;
cin >> n;

vector<int> edges(n);
for (int i = 0; i < n; ++i)
{
cin >> edges[i];
}

int ans = largestSumCycle(n, edges);
cout << ans << endl;

return 0;
}```