m.khooryani's blog

Topological Sort Problem
By m.khooryani, history, 8 years ago, In English

can someone explain more for this problem (510C - Fox And Names)?

I read editorial but I didn't get that

Thanks for your help

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

In this problem you have to find a permutation of characters 'a' to 'z', c1 c2 ... c26 such that if we suppose that c1 is lexicographically smaller than c2, c2 is smaller than c3 and so on, the given names will be sorted lexicographically.

Let's suppose that the characters are nodes of a graph, and an edge between two nodes u and v means that the character u is lexicographically smaller than v.

As I said before every character ci comes before all characters cj (j > i), we need to find an order which makes this constraint satisfied and this is actually a topological sort.

→ Reply