Q1 DAA Mock Contest 3

#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, E, Q;
vector<vector<int>> adj;
vector<int> indegree;
stack<int> ans;
vector<int> vis;

vector<int> toposort(bool ascending) {
    vector<int> ans;
    if(ascending) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < N; i++) {
            if(indegree[i] == 0) {
                pq.push(i);
            }
        }  

        while(!pq.empty()) {
            int curr = pq.top(); pq.pop();
            ans.push_back(curr);
            for(auto v : adj[curr]) {
                indegree[v]--;
                if(indegree[v] == 0) pq.push(v);
            }
        }
    }
    else {
        priority_queue<int> pq;
        for(int i = 0; i < N; i++) {
            if(indegree[i] == 0) {
                pq.push(i);
            }
        }  

        while(!pq.empty()) {
            int curr = pq.top(); pq.pop();
            ans.push_back(curr);
            for(auto v : adj[curr]) {
                indegree[v]--;
                if(indegree[v] == 0) pq.push(v);
            }
        }
    }    
    return ans;
}

void solve_q1() {
    vector<int> r = toposort(true);

    if((int)r.size() != N) {
        cout << -1 << '\n';
        return;
    }  
    
    int n = r.size();
    vector<int> a(n, 1), b(n, 1);
    for(int i = 1; i < n; i++) {
        if(r[i] > r[i - 1]) a[i] = a[i - 1] + 1;
    }        
    for(int i = n - 2; i >= 0; i--) {
        if(r[i] > r[i + 1]) b[i] = b[i + 1] + 1;
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans += max(a[i], b[i]);
    }
    
    cout << ans << '\n';
}

void solve_q2() {
    vector<int> nums = toposort(false);
    int end = 0, far = 0, ans = 0;
    for(int i = 0; i < (int)nums.size() - 1; i++) {
        far = max(far, i + nums[i]);
        if(i == end) {
            ans++;
            end = far;
        }
    }
    cout << ans << '\n';
}

signed main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    cin >> N >> E >> Q;
    adj.resize(N);
    indegree.assign(N, 0);
    for(int i = 0; i < E; i++) {
        int u, v; cin >> u >> v;
        indegree[v]++;
        adj[u].push_back(v);
    }
    if(Q == 1) solve_q1();
    else solve_q2();
    return 0;
}