Saturday, July 30, 2016

Disjoint-set data structure

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int arry[100];

int makeset(int x){
    arry[x]=x;
}

int found(int x){
    if(x==arry[x])
        return x;
    return found(arry[x]);
}

int Union(int x,int y){
    int s1=found(x);
    int s2=found(y);
    if(s1!=s2){
        arry[s2]=s1;
        cout<<"Union between "<<x<<" & "<<y<<endl;
    }
    else
        cout<<"sorry, They are in same set\n";
}


int main()
{

    cout << "Please input your choice\n1. Make Set\n2. Union\n3. Find\n4. End"<< endl;
    while(1){
        cout << "Please input your choice : ";
        int n;
        cin>>n;
        switch(n)
        {
            case 1 : int a;
                     cout<< "Enter element : ";
                     cin>>a;
                     makeset(a);
                     break;
            case 2 : int x,y;
                     cout<< "Enter two element for union : ";
                     cin>>x>>y;
                     Union(x,y);
                     break;
            case 3 : int z;
                     cout<< "Enter find element : ";
                     cin>>z;
                     cout<< "Set no : "<< found(z) <<endl;
                     break;
            case 4 : return 0;
                     break;
            default : cout<<"Wrong input..... Try again"<<endl;
        }
    }

    return 0;
}

No comments:

Post a Comment