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.