4. Diamond Inheritance

Competitive ProgrammingWeek 05

In this lecture we discuss the problem “Diamond Inheritance” from Google Codejam 2012, Round 1C.

You can read up on a proof of the fact that upon running DFS(G,v), we have visited x if and only if x is reachable from v, as mentioned in the lecture (note that we needed only one direction of this equivalence), in these notes (see Claim 1).

You can find the code described in the lecture at this link.