iframe-proxy | Sunbelt Computer Software

Repository navigation

History

#include <iostream>

#include<vector>

using namespace std;

int get_superparent(int x,vector<int>arr,vector<int>par){

if(par[x]==x)return x;

else{

return par[x]=get_superparent(par[x],arr,par);

}

void union_func(int a,int b,int &component,vector<int>arr,vector<int> &par){

int x=get_superparent(a,arr,par);

int y=get_superparent(b,arr,par);

// cout<<"superParent of "<<a<<" is "<<x<<endl;

// cout<<"superparent of "<<b<<" is "<<y<<endl;

if(x!=y){

par[x]=y;

component-=1;

}

int main() {

int n,q,a,b,component;

cin>>n;

vector<int> arr(n);

for(int i=0;i<n;i++)cin>>arr[i];

component=n;

vector<int> par(n);

for(int i=0;i<n;i++)par[i]=i;

cin>>q;

//mark superParent and parent of each node is self

for(int i=0;i<q;i++){

cin>>a>>b;

union_func(a,b,component,arr,par);

}

cout<<component<<endl;

}

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

Disjoint Set Union Algorithm.cpp

Disjoint Set Union Algorithm.cpp

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

Disjoint Set Union Algorithm.cpp

Latest commit

History

Disjoint Set Union Algorithm.cpp

File metadata and controls