v_geta's blog

Problem : Dependency Hell CodeAgon 2017
By v_geta, history, 8 years ago, In English

The link to the problem is given below : CodeAgon Dependency Hell

My Code

I was trying to compare the values in "qu" with multiple criteria :

If the component number for two elements in qu is not the same then it compares them with the their normal values only and does not care about the component number, however if it is same it sorts the members of the same component depending on the level of the node in the graph .

The output i wanted : 8 2 5 6 7 3 4 8 1

The output i actually get : 8 2 5 7 3 4 8 1 6

can i make such comparators ?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best is to find the smallest node u with indegree 0. Then print it and decrement the indegree of all such nodes v such that there is an edge between u and v. Use set<pair<int, int>>.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh right ! Thanks for the alternate approach , can you tell me why mine isn't working ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      First of all, its a directed graph. So it can happen that you give different component number to nodes belonging to same component because of order of calling dfs(node). Eg 1-->3-->5, if I call dfs(3) then dfs(1), {1} and {3,5} are the components formed by your code.

      → Reply