Hello friends can someone tell me how to approach this problem ?
@vijju123 @taran_1407 @vivek_1998299 @meooow @john_smith_3 @aryanc403 @vbt_95
One way could be we make a directed graph with A->B signifying that A is taller than B
then we do a topological sort of the nodes and then count the number of elements such that they do not have an edge between an element in front of them or behind, in the topologically sorted sequences
for example in the test case, the topologically sorted sequence would be
D->C->B->A->E->F->G->H
here A doesn’t have an edge to B and B doesn’t have an edge to A hence they both fell into this catogory
I am not sure of this method. It might work
1 Like
here is what I tried but I am not able to get it working LRKpRA - Online C++0x Compiler & Debugging Tool - Ideone.com
@harrypotter0 saw your code, the n and m are integers separated by comma so cin wont work. another thing when you initized graph the total of vertice are n rather m. i am sure about the implementation of topological sort
I changed input from 8,3 to 8 3 for it to work and correct graph initialization suKL4o - Online C++0x Compiler & Debugging Tool - Ideone.com
okay thanks for this but still the answer is not correct.
D->C->A/B->E->F->G->H THIS IS THE ANSWER.
We have to check for nodes which have indegree 0 and if at any iteration we see 2 or more nodes with 0 indegree than we will say that the positions of these nodes are ambiguous and them to the string as answer and continue checking this until the end. Am I correct in my approach ?
Also I am facing trouble in checking the indegree values of all nodes which are not visited without and then removing 1 out of them (with 0 indegree) and continuing the search. Please help me in this. Thanks 
looks like you are following a different approach then what i stated in the answer.
In your approach you said “2 or more nodes with 0 indegree”. both A and B have 1 indegree and 1 out degree. The only node with zero seems to D. I don’t think it is correct approach. correct me if i am wrong
coming to what i suggested in sequence D->C->A/B->E->F->G->H , we check the adjacent pair of nodes (in the topological sorted sequence ) if they have a edge between them or not, in our sequence A and B are one that do not hence they will be included in the ans
1 Like
Okay I got your approach. But how will we implement this? I mean checking adjacent pair of nodes for an edge between them. How to do this? Bro please implement the code, I will be highly grateful:)