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

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.