WA in Vivek and Party

#1

my code: https://ide.codingblocks.com/s/207807

i am encountering WA in a test case here. stuck here for a day, tried bfs topological sort using set then.
what is the bug in this code.
can you share the dfs approch of the solution?

#2

int indeg[N];
vector topo; //Stores lexicographically smallest toposort
vector g[N];

bool toposort() //Returns 1 if there exists a toposort, 0 if there is a cycle
{
priority_queue<int, vector, greater > pq;
for(int i=1;i<=n;i++)
for(auto &it:g[i])
indeg[it]++;
for(int i=1;i<=n;i++)
{
if(!indeg[i])
pq.push(i);
}
while(!pq.empty())
{
int u=pq.top();
pq.pop();
topo.push_back(u);
for(auto &v:g[u])
{
indeg[v]–;
if(!indeg[v])
pq.push(v);
}
}
if(topo.size()<n)
return 0;
return 1;
}

#3

But in this question we need to store according to the input order not the lexical order? how will this work?

#4

I implemented it as you told with just a comparator funtion, it worked. Thanks, Can you share the dfs approch of doing this Question?

#5

@utkarsh.lal9430310535 topological sort is the dfs implementation of that question only