Untitled

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int V;
int E;
int q;


int sougata(int V, int E, vector<int> indeg, vector<vector<int>> adj){
    // need lexi smallest
    // use min pq
    vector<int> order;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0; i<V; i++){
        if(indeg[i] == 0) pq.push(i);
    }
    
    while(!pq.empty()){
        int curr = pq.top();
        pq.pop();
        order.push_back(curr);
        
        for(auto& el : adj[curr]){
            indeg[el]--;
            if(indeg[el] == 0) pq.push(el);
        }
    }
    if((int)order.size() != V) return -1;
    
    // now doing the cpmputation on the array
    // minimum number of jumps to reach the end of the array
    int end =0, far=0, res=0;
    
    for(int i=0; i<V-1; i++){
        far = max(far, i + order[i]); // one can reach here after jumping from node i;
        if(i==end){
            // if i==0
            res++;
            end = far;
        }
    }
    
    cout << res << '\n';
    return 0;
    
}

int biju(int V, int E, vector<int> indeg, vector<vector<int>> adj){
    // lexi largest
    // meaning from all the topo sorts, find the largest one, in the sense 3-1-2 > 2-1-3
    // opposite for sougata
    // use a pq while doing topo sort
    
    vector<int> order;
    priority_queue<int> pq;
    for(int i=0; i<V; i++){
        if(indeg[i] == 0) pq.push(i);        
    }
    
    while(!pq.empty()){
        int curr = pq.top();
        pq.pop();
        order.push_back(curr);
        
        for(auto& el : adj[curr]){
            indeg[el]--;
            if(indeg[el] == 0) pq.push(el);
        }
    }
    
    // order contains the nodes in the order we need
    
    // now perform the candy algorithm on this vector
    if((int)order.size() != V) return -1; // we can reach all the nodes to form the order
    
    // doing the two pass candy, once from left and once from right
    vector<int> left(V,1), right(V,1);
    for(int i=0; i<V; i++){
        if(order[i] > order[i-1]) left[i] = left[i-1] +1;
    }
    for(int i=V-2; i>=0; i--){
        if(order[i] > order[i+1]) right[i] = right[i+1] +1;
    }
    
    int res = 0;
    for(int i=0; i<V; i++){
        res += max(left[i], right[i]);
    }
    
    cout << res << '\n'; 
    return 0;
    
    
}
signed main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    cin >> V;
    cin >> E;
    cin >> q;
    
    // now make the adj list
    // we get E lines for input
    vector<vector<int>> adj(V);
    
    // make indegree vector as it used for topo sort
    vector<int> indeg(V,0);
    for(int i=0; i<E; i++){
        int from; cin >> from;
        int to; cin >> to;
        adj[from].push_back(to);
        indeg[to]++; // indegree
    }
    
    
    if (q==1) biju(V,E, indeg, adj);
    if (q==2) sougata(V,E, indeg, adj);
    return 0;
}