- for undirected graphs - just check if you ever hit the same node again during [[DFS]], ignoring the prev node - https://leetcode.com/problems/graph-valid-tree/description/ - for directed graph, you do the same thing, but you need a second set after visited - this second set can be called cycle, you add each node at the start of dfs recursion function as normal to cycle like visited, but once you explore all of a node's neighbors you remove it from the cycle - intuition is that after you visit all of a node's neighbors, you should've touched that node again if a cycle was possible at that node - since you never got back to that node, there are no cycles that include that node - note that for directed graphs, you don't want logic to ignore a neighbor if it's a prev node now - cause if you do go backwards to the prev node, it's not an edge you've visited before