How can I group the numbers based on the source and destination?

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:

2 3
4 5
1 4
6 7
5 6

The grouping will look like


Required Output

The number of groups is 2

Test case 2:

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

The grouping will look like


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.

Leave a Reply