### Lain's blog

By Lain, history, 7 months ago,

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.

• -11

 » 7 months ago, # | ← Rev. 2 →   0 The problem is beautiful but the explanations for the solution are really a mess. I suppose that all you have to do is to change the number of the pupils standing in line (1,2,...,n instead p[1],p[2],...,p[n]) and correspondingly in all the pairs (u,v), easy task using a map. After that, imagine the graph having vertices 1,2,3,...,n and directed edges u->v if v
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 This isn't true is it? Consider the queue 1 2 3 4 5. Then I add one edge — 5 -> 2. I can reach one vertex, but I cannot actually move that far ahead. Am I misunderstanding what you're saying?