Not sure if code too slow or judge is taking sides

Правка en1, от svg_af, 2016-03-24 23:38:07

Hello there

I'm trying to solve this problem on LOJ

It's about finding minimum path cover in an acyclic graph that are not vertex disjoint (paths can share vertices)

what I'm doing is calculating the maximum independent set on the graph's transitive closure

I keep getting tle and i thought my approach was too slow but then i found this Chinese blog that uses the same approach and gets accepted on the problem

now i wonder what am i doing that's too slow

here is the code.

specific code steps are :

1- turning graph to dag with computing SSCs (tried using both kosaraju and tarjan)

2- calculating transitive closure of new dag

3- using hopcroft karp on bipartite graph constructed from dag

any help would be really appreciated

Теги graph, tle, loj

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский svg_af 2016-03-24 23:38:07 968 Initial revision (published)