DSU13 - Editorial

editorial
, ,
1

Problem Link - Count Connected Components

Problem Statement:

You are given N nodes and M connections. The task is to determine the total number of connected components in the graph formed by these nodes and connections. Each connected component has a unique leader, and thus the number of leaders will be equal to the number of connected components.

Approach:

This solution employs the Disjoint Set Union (DSU), or Union-Find, to efficiently manage connected components.

  1. Initialization: Two arrays are used:

    • parent[]: Tracks the parent of each node, initialized so each node is its own parent.

    • setSize[]: Stores the size of each component, initialized to 1.

  2. Finding Leaders: The function dsuFind(int a) finds the leader of the component containing node a. If a is its own parent, it is the leader; otherwise, it recursively finds the leader with path compression.

  3. Union of Components: The function dsuUnion(int a, int b) connects two nodes by merging their components. It attaches the smaller component to the larger to maintain balance.

  4. Counting Connected Components: After processing connections, the program counts unique leaders by checking how many nodes are their own parents.

Time Complexity:

  • Union and Find Operations: Amortized O(α(N)), where α is the inverse Ackermann function, making these operations nearly constant.

  • Counting Leaders: O(N), for a single pass through the nodes.

Space Complexity:

  • O(N) for the parent and setSize arrays that store node information.