Disjoint Set | UNION and FIND


This explains the basics of disjoint set data structure from scratch. I have explained all about disjoint set data structure in a simple and easy way to clear your basic understanding on the disjoint set data structure.I have taken intuitive examples and an intuitive algorithm to explain this data structure.I have explained the parent child relationship in a disjoint set by using tree structure for better understanding.I have explained the CODE implementation in the description below.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below.

#include<bits/stdc++.h>
using namespace std;

vector<int> dsuf;
//FIND operation
int find(int v)
{
	if(dsuf[v]==-1)
		return v;
	return find(dsuf[v]);
}

void union_op(int fromP,int toP)
{
	fromP = find(fromP);
	toP = find(toP);
	dsuf[fromP] = toP;
}

bool isCyclic(vector<pair<int,int>>& edge_List)
{
	for(auto p: edge_List)
	{
		int fromP = find(p.first);	//FIND absolute parent of subset
		int toP = find(p.second);

		if(fromP == toP)
			return true;

		//UNION operation
		union_op(fromP,toP);	//UNION of 2 sets
	}
	return false;
}

int main()
{
	int E;	//No of edges
	int V;	//No of vertices (0 to V-1)
	cin>>E>>V;

	dsuf.resize(V,-1);	//Mark all vertices as separate subsets with only 1 element
	vector<pair<int,int>> edge_List;	//Adjacency list
	for(int i=0;i<E;++i)
	{
		int from,to;
		cin>>from>>to;
		edge_List.push_back({from,to});
	}

	if(isCyclic(edge_List))
		cout<<"TRUE\n";
	else
		cout<<"FALSE\n";
	
	return 0;
}

//TIME COMPLEXITY: O(E.V)

Leave a Reply