#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define FOR(i,a,b) for(long long int i=a;i<b;i++)
#define sz(s) (long long int)(s).size()
#define pb push_back
#define mp make_pair
const ll inf = 1000000000;
const ll MOD = 1000000007;
void topologicalSortUtil(vector<vector<ll> > &adj,ll start_node,vector<bool> &visited,stack<ll> &s){
visited[start_node] = true;
for(ll i = 0;i<adj[start_node].size();i++){
if(!visited[adj[start_node][i]]){
topologicalSortUtil(adj,adj[start_node][i],visited,s);
}
}
s.push(start_node+1);
}
void topologicalSort(vector<vector<ll> > &adj,ll num_of_nodes,stack<ll> &s){
vector<bool>visited(num_of_nodes,false);
for(int u=0;u<num_of_nodes;u++){
if(!visited[u]){
topologicalSortUtil(adj,u,visited,s);
}
}
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
register ll i,j,x,y,m,n,t,k,sum=0,max,min,count=0,temp,w,q;
cin>>n>>m;
vector<vector<ll> >adj(n);
while(m--){
cin>>x;
for(i=0;i<x;i++){
cin>>y;
adj[x-1].pb(y-1);
}
}
stack<ll> s;
topologicalSort(adj,n,s);
k = s.size();
ll a[k];
ll prev = 0;
for(i=0;i<k;i++){
a[s.top()-1] = prev;
prev = s.top();
s.pop();
}
for(i=0;i<k;i++){
cout<<a[i]<<"\n";
}
}
I am using topological sorting and stack but getting a wrong answer any help will be appreciated.
I saw there is a queue based version of topological sort but I think it shouldn’t effect the code.
Problem Link: https://www.spoj.com/problems/MAKETREE/
Any help will be greatly appreciated.