I have just studied kahn’s algorithm for topological sort and while practicing, I was not able to get AC in RPLA(Spoj).
Here is my code. It passes the example test cases but getting WA after submitting.
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long
#define mod 1000000007
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
ll power(int x, unsigned int y){
ll res = 1;
while(y > 0){
if(y & 1) res = res * x;
y >>= 1;
x *= x;
}
return res;
}
vi arr[1000];
int in[1000];
struct myCmp {
bool operator() (pair<int, int> a, pair<int,int> b) {
if(a.first < b.first) {
return a.first < b.first;
}else return a.second < b.second;
}
};
void kahn(int nodes) {
priority_queue<pair<int, int> , vector<pair<int,int> >, myCmp > q;
int start = 1;
for(int i = 0; i < nodes; i++) {
if(in[i] == 0) {
q.push({start, i});
cout << start << ' ' << i << '\n';
}
}
start++;
while(!q.empty()) {
int curr = q.top().second;
q.pop();
bool check = false;
for(int child : arr[curr]) {
in[child]--;
if(in[child] == 0) {
check = true;
q.push({start, child});
cout << start << ' ' << child << '\n';
}
}
if(check) start++;
}
}
void solve() {
for(int i = 0; i < 1000; i++) arr[i].clear(), in[i] = 0;
int n, m;
cin >> n >> m;
while(m--) {
int a, b;
cin >> b >> a;
arr[a].pb(b);
in[b]++;
}
kahn(n);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("/ATOMCODES/input.txt", "r", stdin);
freopen("/ATOMCODES/output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
for(int i = 1; i <= t; i++) {
cout << "Scenario #" << i << ':'<< '\n';
solve();
}
}