Two ways to solve the problem:

1. check if graph is connected, then check is there is a loop (starting from any nodes)

2. check if there is a loop (starting from all nodes), then check is #nodes == #edges+1

For both methods, order matters. Otherwise, may have error on cases like

Implementation:

For 1, DFS, note that the two steps can be combined

For 2, union find, faster

Same idea for

**[LC 323]****Number of connected component in a undirected graph**:1. DFS is easy

2. For union find: standard solution with path compression

Advertisements