This code implements a disjoint set data structure. It allows...

December 8, 2023 at 02:55 AM

#include <stdio.h>

#define MAX_SIZE 1000 // Adjust the maximum size as needed

int parent[MAX_SIZE]; // Array to store parent information
int size; // Declaration of size variable

// Initialize the disjoint set
void initialize(int n) {
    size = n; // Initialize the size
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

// Find the root/parent of a set
int find(int x) {
    if (parent[x] == x)
        return x;
    return find(parent[x]);
}

// Perform the union operation
void unionn(int a[], int u, int v) {
    int rootU = find(u);
    int rootV = find(v);

    if (rootU != rootV) {
        // Make one of the roots the parent of the other
        parent[rootU] = rootV;

        // Update the values in the array based on the union
        for (int i = 0; i < size; i++) {
            if (find(i) == rootU) {
                a[i] = a[v];
            }
        }
    }
}

int main() {
    // Take input for the size of the array
    printf("Enter the size of the array: ");
    scanf("%d", &size);

    // Initialize the array and disjoint set
    int array[MAX_SIZE];
    printf("Enter %d elements for the array: ", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &array[i]);
    }

    initialize(size);

    // Take input for the union operations
    int u, v;
    printf("Enter the indices (u v) for union operation (or -1 -1 to exit): ");
    while (scanf("%d %d", &u, &v) == 2 && (u != -1 && v != -1)) {
        if (u >= 0 && u < size && v >= 0 && v < size) {
            unionn(array, u, v);
            printf("Array after union operation: ");
            for (int i = 0; i < size; i++) {
                printf("%d ", array[i]);
            }
            printf("\nEnter the indices (u v) for union operation (or -1 -1 to exit): ");
        } else {
            printf("Invalid indices. Enter valid indices (or -1 -1 to exit): ");
        }
    }

return 0;
}

This code implements a disjoint set data structure. It allows the user to perform union operations on elements of an array. The code initializes the array and the disjoint set, and then takes input from the user to perform union operations on the array elements. The code also updates the values in the array based on the union operation.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr