Блог пользователя m.khooryani

Topological Sort Problem
Автор m.khooryani, история, 9 лет назад, По-английски

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

I read editorial but I didn't get that

Thanks for your help

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить