Connected Components in a Graph | HackerRank Solution

 Connected Components in a Graph

Problem

Given n, i.e. total number of nodes in an undirected graph numbered from 1 to n and an integer e, i.e. total number of edges in the graph. Calculate the total number of connected components in the graph. A connected component is a set of vertices in a graph that are linked to each other by paths.

Input Format:

First line of input line contains two integers n and e. Next e line will contain two integers u and v meaning that node u and node v are connected to each other in undirected fashion. 

Output Format:

For each input graph print an integer x denoting total number of connected components.

Constraints:

All the input values are well with in the integer range.

Sample Input

8 5
1 2
2 3
2 4
3 5
6 7

Sample Output

3

Time Limit: 5

Memory Limit: 256

Source Limit:

	#include <bits/stdc++.h>
	using namespace std;
	class Union{
	public:
	vector<int>par;
	Union(int n){
	for (int i = 0; i < n; i++)
	{
	par.push_back(-1);
	}
	}
	int findPar(int x){
	return par[x]<0 ? x : par[x]=findPar(par[x]);
	}
	void merge(int x,int y){
	if((x=findPar(x))==(y=findPar(y))){
	return;
	}
	if(par[y]<par[x])swap(x,y);
	par[x]+=par[y];
	par[y]=x;
	}
	int total(){
	int ans=0;
	for (int i = 1; i < par.size(); i++)
	{
	if(par[i]<0)ans++;
	}
	return ans;
	}
	};
	void solve() {
	int n,e;
	cin>>n>>e;
	int v[e][e];
	Union dsu=Union(n+1);
	for (int i = 0; i < e; i++)
	{
	cin>>v[i][0];
	cin>>v[i][1];
	dsu.merge(v[i][0],v[i][1]);
	}
	cout<<dsu.total();
	}
	int32_t main()
	{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	clock_t z = clock();
	int t = 1;
	// cin >> t;
	while (t--) solve();
	return 0;
	}

Made with ❤ by Raunit Verma Rate Us 5⭐ Here