1) yes. 2) is ok (with a hash table instead of an array to have linear execution time), but doesn't run in constant space unlike 1), or you could mark the nodes when you visit them.