Answer: SALESFORCE | Disjoint Set Union and Graph Connectivity Analysis | SWE OA 2022

Approach This problem can be solved efficiently using the Disjoint Set Union (DSU) data structure, also known as Union-Find. Key Idea Initially: Each node forms its own component. So: components = n Whenever two nodes belong to different components, we merge them. Every successful merge reduces the component count by: 1 Strategy Step 1 Initialize: parent[i] = i Each node is its own parent. Step 2 Use Path Compression inside find() to optimize searches. Step 3 Use Union by Rank ...