There are N – pair of numbers given in the problem, objective is to find the number of groups can be found using the relation.

Test case 1:

5
2 3
4 5
1 4
6 7
5 6

The grouping will look like

2->3
1->4->5->6->7

Required Output

The number of groups is 2

Test case 2:

6
2 4
3 1
6 5
7 6
9 8
22 32

The grouping will look like

2->4
3->1
7->6->5
9->8
22->32

Required output

The number of groups is 5

I hope the question is clear to you guys, I don’t know where to start or how to google it and find the relevant article, If you know any concepts to solve this question, kindly be gentle in the comments, I am a noob in dsa 🙂

>Solution :

You are looking for the connected components in a graph.

A simple algorithm:

* First, build a structure that makes it easy and fast to get the direct neighbours of a given node.

* Initialise a set Unvisited, originally containing all nodes.

* Loop until Unvisited is empty:
    * remove a node u from Unvisited
    * initialise a Queue, originally containing u
    * initialise a new Connected_Component, originally empty
    * Loop until Queue is empty:
        * remove a node v from the Queue
        * add v to Connected_Component
        * remove all Unvisited neighbours of v from Unvisited and add them to the Queue

Relevant references:

• Connected component;
• Queue; "queue" is generally understood to mean "first-in first-out", but in this particular case the order doesn’t matter.
• Adjacency list, a structure representing a graph by giving the list of neighbours of every node.