Union-Find Data Structure

Union-Find (Disjoint Set Union) is a data structure that tracks a set of elements partitioned into disjoint sets. It supports two primary operations:

• Find: Determine which set a particular element belongs to
• Union: Merge two sets into a single set

This article demonstrates these concepts through two classic competitive programming problems.

Problem B: Connected Roads

Problem Statement

Given n cities and m existing road connections between pairs of cities, determine the minimum number of additional roads needed to connect all cities into a single network.

Analysis

After processing the m existing connections, the cities form several disjoint sets. The answer is simply components - 1, where components is the count of distinct sets among the n cities.

To find the number of components, iterate through all cities. If a city's parent pointer points to itself, it is a root node and represents one component.

Implementation

#include <cstdio>
#define MAX_CITIES 1005

int parent[MAX_CITIES];
int cityCount, roadCount;

int findRoot(int node) {
    if (node == parent[node]) return node;
    int root = findRoot(parent[node]);
    parent[node] = root;  // path compression
    return root;
}

void mergeSets(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

int main() {
    int cityA, cityB;
    while (scanf("%d", &cityCount) && cityCount) {
        scanf("%d", &roadCount);
        
        for (int i = 1; i <= cityCount; i++) {
            parent[i] = i;
        }
        
        while (roadCount--) {
            scanf("%d%d", &cityA, &cityB);
            mergeSets(cityA, cityB);
        }
        
        int componentCount = 0;
        for (int i = 1; i <= cityCount; i++) {
            if (i == parent[i]) componentCount++;
        }
        
        printf("%d\n", componentCount - 1);
    }
    return 0;
}

Key points:

• Initialize parent[i] = i for all nodes before processing connections
• Use 1-based indexing since input nodes start from 1
• Path compression optimizes subsequent find operations

Problem D: Maximum Friend Group

Problem Statement

A room contains up to 10,000,000 people. Given n friendship relationships (if 1 2 is given, person 1 and person 2 are friends), find the size of the largest group where friends of friend are also considered friends.

Analysis

The problem requires finding the maximum cardinality among all disjoint sets after processing the friendship relationships.

Three critical considerations:

1. Initialize all potential nodes since the maximum person ID is not known from input
2. Use findRoot(i) instead of parent[i] when counting group sizes, as path compression may not have been applied to all node
3. Limit iteration bounds to the maximum ID encountered to avoid TLE

Implementation

#include <cstdio>
#include <cstring>

#define MAX_PERSONS 10000005

int parentArr[MAX_PERSONS];
int groupSize[MAX_PERSONS];

int findRoot(int node) {
    if (node == parentArr[node]) return node;
    int root = findRoot(parentArr[node]);
    parentArr[node] = root;
    return root;
}

void joinGroups(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX != rootY) {
        parentArr[rootX] = rootY;
    }
}

int main() {
    int relationshipCount, id1, id2;
    int maxId = 0, largestGroup = 1;
    
    while (scanf("%d", &relationshipCount) != EOF) {
        memset(groupSize, 0, sizeof(groupSize));
        maxId = 0;
        largestGroup = 1;
        
        for (int i = 1; i <= MAX_PERSONS; i++) {
            parentArr[i] = i;
        }
        
        for (int i = 0; i < relationshipCount; i++) {
            scanf("%d%d", &id1, &id2);
            joinGroups(id1, id2);
            if (id1 > maxId) maxId = id1;
            if (id2 > maxId) maxId = id2;
        }
        
        for (int i = 1; i <= maxId; i++) {
            groupSize[findRoot(i)]++;
        }
        
        for (int i = 1; i <= maxId; i++) {
            if (groupSize[i] > largestGroup) {
                largestGroup = groupSize[i];
            }
        }
        
        printf("%d\n", largestGroup);
    }
    return 0;
}

Key points:

• Pre-initialize the entire parentArr array to handle any ID up to the maximum
• Always call findRoot(i) when calculating group sizes, never directly use parentArr[i]
• Iterate only up to maxId to reduce time complexity from O(maxn) to O(relationships)

Summary

The Union-Find structure efficiently handles dynamic connectivity problems. Path compresion during find operations ensures nearly constant time amortized complexity. When counting set sizes, always use the find operation to account for uncompressed paths.