# Untitled

unknown
c_cpp
a month ago
3.0 kB
1
Indexable
Never
```#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);

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);

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

// 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;