DisjointSetUnion.cpp

#include<bits/stdc++.h>

using namespace std;

int parent[105];


struct side
{

    int from;
    int to;

} get;


int findset(int n)
{
    if(parent[n]==n)
    {
        return n;
    }
    return parent[n]=findset(parent[n]);

}


void setunion(int a,int b)
{
    int x = findset(a);
    int y = findset(b);
    if(x==y)
    {
        cout<<"They ar already friends"<<endl;
    }
    else
    {
        parent[a]=b;
    }

}





int main()
{
    ios_base::sync_with_stdio(false);
    vector<side>vec;

    int a,b,j,ara[1000];
    int n;
    cin>>n;

    for(int i =1; i<=n; i++)
    {
        parent[i]=i;
    }

    for(int i = 0; i<n; i++)
    {
        cin>>a>>b;
        get.from = a;
        get.to = b;
        vec.push_back(get);
    }

    for(int i = 0; i<n; i++)
    {
        int u = vec[i].from;
        int v = vec[i].to;
        setunion(u,v);
    }

    for(int i = 1; i <= 10; i++) printf("Parent of %d is %d\n", i, parent[i]);
    cout << endl;
    for(int i = 1; i <= 10; i++) printf("Set of %d is %d\n", i, findset(i)); // call findset for 10 elements
    cout << endl;
    for(int i = 1; i <= 10; i++) printf("Parent of %d is %d\n", i, parent[i]);




    return 0;
}