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