[LC 261] Graph valid tree

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s