disjoiintset.cpp

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

class DisjoinSet{
	vector<int> parent, rank;
public:
	DisjoinSet(int n){
		parent.resize(n,0);
		rank.resize(n,0);
		for(int i=0;i<n;i++){
			parent[i]=i;
		}
	}

	int findUParent(int u){
		if(u == parent[u]){
			return u;
		}
		else{
			return parent[u] = findUParent(parent[u]);
		}
	}

	void UnionByRank(int u, int v){
		int u_p_v = findUParent(v);
		int u_p_u = findUParent(u);
		if(u_p_u == u_p_v){
			return ;
		}
		if(rank[u_p_u] > rank[u_p_v]){
			parent[u_p_v] = u_p_u;
		}
		else if(rank[u_p_v] > rank[u_p_u]){
			parent[u_p_u] = u_p_v;
		}
		else{
			parent[u_p_u] = u_p_v;
			rank[u_p_v]++;
		}
	}

};

int main(){
	int n;
	cin>>n;
	DisjoinSet disjointSet(7);
	for(int i=0;i<n;i++){
		int sou, des;
		cin>>sou>>des;
		disjointSet.UnionByRank(sou,des);
	}
	if(disjointSet.findUParent(1) == disjointSet.findUParent(4)){
		cout<<"Both belongs to same component";
	}
	else{
		cout<<"Different components";
	}
}