Untitled

mail@pastecode.io avatar
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;
}
Leave a Comment