_notpalindrome_'s blog

By _notpalindrome_, history, 18 months ago, In English,

Recently I have learned topological sort using defth first search(dfs). I am trying to solve the problem for a while but cant understand, What should be my first approach? Can anyone explain me step by step. Any hint would be greatly appreciated. Thanks. :) Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2001

  • Vote: I like it
  • 0
  • Vote: I do not like it

18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

You should build a graph. Nodes are strings and vertexes are given pairs of strings. You can transform strings into numbers using array s[i] — ith string in input, for example. Then you can build vertexes as in usual graph using this array in O(N*M)(may be faster using std::map) Now you have a graph and can topological sort it.