Count the number of groups formed in a graph of friends

Approach

We can approach this problem by forming a group, in which the students will be the vertices and the relationship between them will be the edges. 

😎 To solve the first part of the problem - Find the number of existing groups - we just need to find the number of connected components in the graph. This can be done easily by using the DFS Algorithm. We need to count the number of times a Depth-First-Search starts from the unvisited vertex of friends. 

          🤓 Initialize a visited array, so store whether the vertex was visited or not. 

😁 For a vertex v, if visited[v] is equal to the zero, then call DFS on it, else move to the next vertex. 

🤠 For every DFS traversal change the visited[v] to 1. 

🧐 Increment the count of DFS traversal.

🤩 The other part - Find the number of new groups that can be formed - we can use the formulae (N₁)*(N₂)*...(N_n), where N_i is the number of students in the i^th group.

Note: The graph will be an undirected graph. 

For the above sample example, the below image shows the graph structure and the adjacency matrix. 

Implementation in C++

// C++ program to count number of existing
 groups and number of new groups that can
 be formed.
#include <bits/stdc++.h>
using namespace std;

class Graph {
	int V; // No. of vertices
	
	// Pointer to an array containing
	// adjacency lists
	list<int>* adj;
	
	int countUtil(int v, bool visited[]);
public:
	Graph(int V); // Constructor
	
	// function to add an edge to graph
	void addRelation(int v, int w);
	void countGroups();
};

Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}

// Adds a relation as a two way edge of
// undirected graph.
void Graph::addRelation(int v, int w)
{
	// Since indexing is 0 based, reducing
	// edge numbers by 1.
	v--;
	w--;
	adj[v].push_back(w);
	adj[w].push_back(v);
}

// Returns count of not visited nodes reachable
// from v using DFS.
int Graph::countUtil(int v, bool visited[])
{
	int count = 1;
	visited[v] = true;
	for (auto i=adj[v].begin(); i!=adj[v].end(); ++i)
		if (!visited[*i])
			count = count + countUtil(*i, visited);
	return count;	
}

// A DFS based function to Count number of
// existing groups and number of new groups
// that can be formed using a member of
// every group.
void Graph::countGroups()
{
	// Mark all the vertices as not visited
	bool* visited = new bool[V];
	memset(visited, 0, V*sizeof(int));

	int existing_groups = 0, new_groups = 1;
	for (int i = 0; i < V; i++)
	{
		// If not in any group.
		if (visited[i] == false)
		{
			existing_groups++;
			
			// Number of new groups that
			// can be formed.
			new_groups = new_groups *
					countUtil(i, visited);
		}
	}
	
	if (existing_groups == 1)
		new_groups = 0;
	
	cout << "No. of existing groups are "
		<< existing_groups << endl;
	cout << "No. of new groups that can be"
			" formed are " << new_groups
		<< endl;
}

// Driver code
int main()
{
	int n = 6;

	// Create a graph given in the above diagram
	Graph g(n); // total 6 people
	g.addRelation(1, 2); // 1 and 2 are friends
	g.addRelation(3, 4); // 3 and 4 are friends
	g.addRelation(5, 6); // 5 and 6 are friends

	g.countGroups();

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

// Java program to count number of existing groups and number of new groups that can be formed.

import java.util.*;
import java.io.*;

class Graph{

	// No. of vertices
	private int V;
	
	// Array of lists for Adjacency
	// List Representation
	private LinkedList<Integer> adj[];

	// Constructor
	Graph(int v)
	{
		V = v;
		adj = new LinkedList[V];
	
		for(int i = 0; i < V; i++)
		{
			adj[i] = new LinkedList();
		}
	}
	
	// Adds a relation as a two way edge of undirected graph.
	public void addRelation(int v, int w)
	{
	
		// Since indexing is 0 based, reducing
		// edge numbers by 1.
		v--;
		w--;
		adj[v].add(w);
		adj[w].add(v);
	}

	// Returns count of not visited nodes reachable from v using DFS.
	int countUtil(int v, boolean visited[])
	{
		int count = 1;
		visited[v] = true;
	
		// Recur for all the vertices adjacent
		// to this vertex
		Iterator<Integer> i = adj[v].listIterator();
		while (i.hasNext())
		{
			int n = i.next();
			if (!visited[n])
				count = count + countUtil(n, visited);
		}
		return count;
	}
	
	// A DFS based function to Count number of existing groups and number of new groups that can be formed using a member of every group.
	void countGroups()
	{
	
		// Mark all the vertices as not
		// visited(set as false by default
		// in java)
		boolean visited[] = new boolean[V];
		int existing_groups = 0, new_groups = 1;
	
		for(int i = 0; i < V; i++)
		{
		
			// If not in any group.
			if (visited[i] == false)
			{
				existing_groups++;

	
				// Number of new groups that
				// can be formed.
				new_groups = new_groups *
							countUtil(i, visited);
			}
		}

		if (existing_groups == 1)
			new_groups = 0;
		
	
		System.out.println("No. of existing groups are " +
						existing_groups);
		System.out.println("No. of new groups that " +
						"can be formed are " +
						new_groups);
	}
	
	public static void main(String[] args)
	{
		int n = 6;

	
		// Create a graph given in
		// the above diagram
		Graph g = new Graph(n); // total 6 people
		g.addRelation(1, 2); // 1 and 2 are friends
		g.addRelation(3, 4); // 3 and 4 are friends
		g.addRelation(5, 6); // 5 and 6 are friends

	
		g.countGroups();
	}
}

You can also try this code with Online Java Compiler

Run Code

Implementation in Python

# Python3 program to count number of
# existing groups and number of new
# groups that can be formed.
class Graph:
	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]
	
	# Adds a relation as a two way
	# edge of undirected graph.
	def addRelation(self, v, w):
		
		# Since indexing is 0 based,
		# reducing edge numbers by 1.
		v -= 1
		w -= 1
		self.adj[v].append(w)
		self.adj[w].append(v)
	
	# Returns count of not visited
	# nodes reachable from v using DFS.
	def countUtil(self, v, visited):
		count = 1
		visited[v] = True
		i = 0
		while i != len(self.adj[v]):
			if (not visited[self.adj[v][i]]):
				count = count + self.countUtil(self.adj[v][i],
													visited)
			i += 1
		return count
	
	# A DFS based function to Count number
	# of existing groups and number of new
	# groups that can be formed using a
	# member of every group.
	def countGroups(self):
		
		# Mark all the vertices as
		# not visited
		visited = [0] * self.V
	
		existing_groups = 0
		new_groups = 1
		for i in range(self.V):
			
			# If not in any group.
			if (visited[i] == False):
				existing_groups += 1
				
				# Number of new groups that
				# can be formed.
				new_groups = (new_groups *
							self.countUtil(i, visited))
		
		if (existing_groups == 1):
			new_groups = 0
		
		print("No. of existing groups are",
						existing_groups)
		print("No. of new groups that",
			"can be formed are", new_groups)

# Driver code
if __name__ == '__main__':

	n = 6

	# Create a graph given in the above diagram
	g = Graph(n) # total 6 people
	g.addRelation(1, 2) # 1 and 2 are friends
	g.addRelation(3, 4) # 3 and 4 are friends
	g.addRelation(5, 6) # 5 and 6 are friends

	g.countGroups()

You can also try this code with Online Python Compiler

Run Code

Output

No. of existing groups are 3

No. of new groups that can be formed are 8. 

Time Complexity

 O(N + R) where N is the number of people and R is the number of relations.

Space Complexity

O(N x N), where N is the number of vertices. We are storing the adjacency matrix which is (N x N) as we will be storing all the vertices.

Must Read C++ vs Java

Frequently Asked Questions

What is a Graph?

A Graph is a set of points called vertices, connected by edges. The vertices represent the data to be stored and the edges are the relationships between the vertices. 

What is an Adjacency Matrix? 

An adjacency matrix is a square two dimensional boolean matrix such that for adjacency matrix adj[][] if adj[i][j] is equal to one, there exists an edge between the vertex i and j.

What is the DFS algorithm?

The Depth-First-Search Algorithm traverses the tree or graph data structure as far as possible along the branch without backtracking. 

Conclusion

Pat yourself on the back for finishing this article. We discussed the solution of how to find the count of the number of groups formed in a graph of friends and its implementation in C++, Java and Python. 

If you liked this article and want to learn more, please read some of our articles - 

1.  Floyd’s Cycle Detection 
2.  0-1 BFS in Graph
3. Java List Iterator
4.  DFS traversal
5.  M-coloring Problem

Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.

If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to the Coding Ninjas Studio, our practice platform.

We wish you Good Luck!🎈 Please upvote our blog 🏆 and help other ninjas grow.