Happy Group - Mindstormer April 20

Happy Group

Question Breif

A group of blocks is said to be connected if we can reach from any given block to any other block in the same group, and this group is known as happy group . Given N blocks (numbered from 1 to N) and two lists of size M (u and v) denoting block u[i] is connected to block v[i] and vice versa . Can you count the number of happy groups. 

Note: A block is always connected to himself

Link to question:
https://www.hackerrank.com/contests/mindstormer-apr20/challenges/happy-group

Approach:

Graph- BFS

• we keep arrays u and v as given in the question.
• We create a  2D array-edges(ed) which keep record of whichblocks are connected with each other.
• We maintain visited array(vis) that keep record of which block is visited and which is left.

Further explanation is in the comments with the code.

The main thing used is BFS and graph to solve this problem

	#include<iostream>
	#include<vector>
	#include<queue>
	using namespace std;
	// for bfs we have to use queue data structure and we are marking all the blocks as visted that can be visited from the starting node
	void helperbfs(int **ed,int * vis,int s,int V){// (edge array,visited array,starting node,no. of vertex/blocks)
	vector<int> v;
	queue<int> q;
	q.push(s);
	v.push_back(s);
	while(!q.size()==0){
	int r=q.front();
	q.pop();
	v.push_back(r);
	vis[r]=1;
	for(int j=0;j<V;j++){
	if(r==j){
	continue;
	}
	if(ed[r][j]==1){
	if(vis[j]==1){
	continue;
	}else{
	vis[j]=1;
	q.push(j);
	}
	}
	}
	}
	}
	// in bfs we are creating a visited array which keep mark of which node is included in some group or not.
	int bfs(int **ed,int n){
	int *vis=new int[n];
	for(int i=0;i<n;i++){
	vis[i]=0;
	}
	int count=0;
	for(int i=0;i<n;i++){
	if(!vis[i]){
	helperbfs(ed,vis,i,n);// print function is actually performing th function of bfs helperbfs(edge array,visited aray,block no.,no. of blocks)
	count++;// every time print function is called it states that there is a new group so we increment count.
	}
	}
	return count;// we return the no. of groups
	}
	//In solve method we are just creating the edge array we are marking 1 where the edge exist between two blocks.
	// And then we are calling the bfs(breadth first search approach for which we a function above)
	int solve(int n,int m,vector<int>u,vector<int>v)
	{
	int **ed=new int*[n];// creating edge array
	for(int i=0;i<n;i++){
	ed[i]=new int[n];
	for(int j=0;j<n;j++){
	ed[i][j]=0;
	}
	}
	for(int i=0;i<m;i++){
	ed[u[i]-1][v[i]-1]=1;
	ed[v[i]-1][u[i]-1]=1;
	}
	return bfs(ed,n); // calling dfs function bfs(edge array, no. of nodes) it will return the no. of groups
	}
	// Here we are just getting the input from user as per the question requirement
	int main()
	{
	int n,m;
	vector<int>u,v;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
	int x;
	cin>>x;
	u.push_back(x);
	}
	for(int i=0;i<m;i++)
	{
	int x;
	cin>>x;
	v.push_back(x);
	}
	cout<<solve(n,m,u,v)<<endl; // Solve method called
	}

view raw HappyGroup.cpp hosted with ❤ by GitHub