Transitive closure and Floyd's algorithm

Revision en1, by sensei11, 2015-12-24 19:45:31

I was solving https://community.topcoder.com/stat?c=problem_statement&pm=12692&rd=15698. Editorial : apps.topcoder.com/wiki/display/tc/SRM+586 I could follow the editorial till the section on "Transitivity". I don't understand how using Floyd's algorithm ensures that all constraints are satisified and what exactly is Transitive Closure. I looked up the term in graph theory though I don't see how it applies in this scenario.

Any help regarding the above matter would be appreciated.

Tags graphs, topcoder, floyd warshall

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sensei11 2015-12-24 19:46:38 6
en1 English sensei11 2015-12-24 19:45:31 538 Initial revision (published)