GeeksForGeeks-Problem/02 February Largest Sum Cycle at main · Michael-Calce/GeeksForGeeks-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution
{
  public:
  vector<vector<int>> v;
  vector<int> vis,par,tmp;
  long long dfs(int node,int p=-1){
    vis[node]=1;
    par[node]=p;
    tmp.push_back(node);
    for(auto i:v[node]){
      if(vis[i]==0){
        long long z=dfs(i,node);
        if(z!=-1){
          return z;
        }
      }
      else if(vis[i]==1){
        long long sum=i;
        while(node!=i){
          sum+=node;
          node=par[node];
        }
        if(node==i)
          return sum;
        return -1;
      }
    }
    return -1;
  }
  long long largestSumCycle(int N, vector<int> Edge)
  {
    long long ans=-1;
    vis=vector<int>(N);
    v=vector<vector<int>>(N);
    par=vector<int>(N);

    for(int i=0;i<N;i++){
      if(Edge[i]!=-1){
        v[i].push_back(Edge[i]);
      }
    }

    for(int i=0;i<N;i++){
      if(!vis[i]){
        ans=max(ans,dfs(i));
        for(auto j:tmp){
          vis[j]=2;
        }
        tmp.clear();
      }
    }

    return ans;
  }
};