[Union Find] Number of Connected Components in an Undirected Graph

[sudosf]

Problem

Given n nodes and a list of undirected edges, return the number of connected components in the graph.

References

• LeetCode: https://leetcode.com/problems/count-the-number-of-complete-components/description/
• GFG: https://www.geeksforgeeks.org/problems/connected-components-in-an-undirected-graph/1
• Sheet: https://www.risingbrain.org/sheet#graph (Union Find [Two Pointer] Move Zeroes #4)
• Parent: Pattern: Graph - Union Find (Disjoint Set) #126

Difficulty

🟡 Medium

Companies

Microsoft, Facebook, Morgan Stanley

Notes

Language: Java
Classic Union Find application. Also solvable with BFS/DFS counting components.