Graph Solution for 1136D

Revision en1, by Lain, 2020-08-30 07:19:22

I was reading the editorial for 1136D, and solution 2 talks about a graph-based solution. I didn't completely understand it. I understood the graph they built(I think), and the answer is the number of unreachable vertices, but what is this "standard algorithm" called DFS by complement graph? I've never heard of it, and I just see a bunch of papers on Googling, which leads me to believe it isn't as standard as the editorialist claims it is. Also, if this is the standard definition of a complement graph, why is the graph described in the problem the complement of the provided graph? Is it assuming I remove all the edges where $v$ is behind $u$?

I've posted this blog since comments about the same on the editorial went ignored, so I hope this will reach more people. Thanks in advance.

History

Revisions

Rev. Lang. By When Δ Comment
en1 Lain 2020-08-30 07:19:22 913 Initial revision (published)