DSU

#include<stdio.h>
#include<stdlib.h>

#define N 64
int U[N];

void Initilize()
{
    for(int i=0 ; i < N ; i++)
    {
        U[i] = i;
    }
}

typedef struct Sub_Set
{
    int no;
    unsigned ss[N/sizeof(int)];
    struct Sub_Set *nxt;
}Sub_Set;

Sub_Set* Search_Set(Sub_Set *head, int set_no)
{
    Sub_Set *x = head;
    while(x != NULL)
    {
        if(x->no == set_no)
        {
            return x;
        }
        x = x->nxt;
    }
    return NULL;
}

void Add_Element(Sub_Set **ptr)
{
    int ans = 1, e;
    for(int i=0;i<N && ans==1;i++)
    {
        printf("\nEnter the element : ");
        scanf("%d", &e);
        if(e>=0 && e<N)
        {
            //(*ptr)->ss[e / 32] += 1 << (e % 32);
            (*ptr)->ss[e / 32] |= 1 << (e % 32);

        }
        else
        {
            printf("\nInvalid!");
        }
        printf("\n\n Continue? ");
        scanf("%d", &ans);
    }
}

void New_Subset(Sub_Set **head)
{
    static int c = 1;
    int e, ans = 1;
    Sub_Set *ptr;
    ptr = (Sub_Set*)malloc(sizeof(Sub_Set));

    for(int i=0;i<N/sizeof(int);i++)
    {
        ptr->ss[i] = 0;
    }
    ptr->no = c++;
    Add_Element(&ptr);

     if(*head == NULL)
    {
        *head = ptr;
    }
    else
    {
        Sub_Set *x = *head;
        while(x->nxt!=NULL)
            x=x->nxt;
        x->nxt = ptr;
    }

}

void Add_to_Existing(Sub_Set **head)
{
    int set_no;
    Sub_Set *x;
    printf("\nEnter the Set No. : ");
    scanf("%d", &set_no);
    x = Search_Set(*head, set_no);
    if(x == NULL)
    {
        printf("\nNo such Set");
        return;
    }
    Add_Element(&x);
}

void Display(Sub_Set *x)
{
    if(x==NULL)
        return;
    printf("Set No. %d ---> { ",x->no);

    for(int i=0;i<N/sizeof(int);i++)
    {
        unsigned int c = 0, h = x->ss[i];
        while(h!=0)
        {
            if(h % 2 == 1)
                printf("%d ", c+32*i);
            h = h/2;
            c++;
        }
    }
    printf("}\n");
}

void Display_All(Sub_Set *head)
{
    if(head == NULL)
    {
        printf("\n<No Sub-sets>");
        return;
    }
    Sub_Set *x = head;
    printf("\n\t<---Sub-sets--->:\n");
    while(x != NULL)
    {
        Display(x);
        x=x->nxt;
    }
}

int Check_Set(Sub_Set *x, int s)
{
    if((x->ss[s/32] | 1<<(s%32)) == x->ss[s/32])
        return 1;
    else
        return 0;
}

void Present_or_not(Sub_Set *head)
{
    int set_no, s, flag = -1;
    printf("\nEnter the Set no. : ");
    scanf("%d", &set_no);
    printf("\nEnter the no to be searched : ");
    scanf("%d", &s);

    Sub_Set *x = Search_Set(head,set_no);

    if(x == NULL)
    {
        printf("\nNo such Set");
        return;
    }

    if(Check_Set(x, s))
        printf("\nPresent!");
    else
        printf("\nNot Present!");
}



void main()
{
    unsigned int b = 1<<31;
    printf("\nb = %u ",b);
    Sub_Set *head = NULL;
    int a;
    while(1)
    {
        printf("\n\n1. Add New Subset\n2. Display All\n3. Present or Not\n4. Add Existing\n0. Exit");
        printf("\n Enter your choice : ");
        scanf("%d", &a);
        switch(a)
        {
            case 1: New_Subset(&head);
                    break;
            case 2: Display_All(head);
                    break;
            case 3: Present_or_not(head);
                    break;
            case 4: Add_to_Existing(&head);
                    break;
            case 0: return;
            default: continue;
        }
    }
}