LC: 323. Number of Connected Components in an Undirected Graph - spiralgo/algorithms GitHub Wiki

323. Number of Connected Components in an Undirected Graph

The Essence:

When some set of nodes are in a connected component (in an undirected graph), this implies 2 things:

1. When this component is fully traversed starting from any node, all the other nodes in this component will be visited.
2. For the nodes in this connected component, a common parent/root/pivot node that indicates this connected component can be chosen.

Details:

Using the first implication, an algorithm that traverses all unvisited connected component and marks all the nodes there visited can be used. This can be implemented using both BFS and DFS.

Using the second implication, the problem-solver can apply the Disjoint-set/Union-find data structure to solve this problem. For this, it is important to understand that:

• If a new given edge connects 2 previously discrete nodes, then the number of connected components decreases.
• If we have [0,1] and [2,3], we have 4 nodes, and 2 edges reduces the number of connected components to 2.
• If we connect 2 and 1 for example, the number will reduce to 1.