1 DFS for graph

1.1 undirected graph

https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

Note that we only need one dict! This is easier than Detect Cycle in a directed Graph, where we need 2 dicts.

Note that if the input graph may be disconnected, we just need to try starting from all nodes.

1.2 directed graph

ref: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/.

Note that we need 2 dicts!

Note that if the input graph may be disconnected, we just need to try starting from all nodes.

Exercise:

269. Alien Dictionary