forming sets of numbers

[mnnsa]

how to form sets of numbers in c++ if the input we give is like this

3//number of pairs to input
1 2 // belong to same set
4 7 //belong to same set
8 7// belong to same set

Final sets formed are : 2
set1: 1 ,2
set2: 4, 8, 7

[Repeater]

Something like:

create vector of vector<int>
Read each line -> put numbers into a vector<int> -> add vector<int> to vector<vector<int>>

[lastchance]

@mnsa,
Could you provide a better explanation of your problem?

5 //number of pairs to input
1 2 // belong to same set
4 7 //belong to same set
8 7// belong to same set

Final sets formed are : 2
set1: 1 ,2
set2: 4, 8, 7

Start with:

5 //number of pairs to input

Well, you appear to be inputting THREE pairs, not five?


Then

Final sets formed are : 2
set1: 1 ,2
set2: 4, 8, 7

Well, from what you have explained thus far,

Final sets formed are : 1
set1: 1 ,2, 4, 7, 8

would be just as good.


Please provide a better explanation.

[mnnsa]

Yes it's 3 not 5 by mistake I wrote 5

[lastchance]

OK then, what is your rule for forming sets? Why is

Final sets formed are : 1
set1: 1, 2, 4, 7, 8

not a solution?


Are you trying to maximise the number of sets, or what?

[mnnsa]

Final set formed are
Set 1: 1,2
Set 2: 4,8,7

As in input we take pairs as input and they belong to same set .
U understood ?

[lastchance]

mnsa wrote:

As in input we take pairs as input and they belong to same set .
U understood ?

No, U misunderstand.

set1: 1, 2, 4, 7, 8

As you can see, trivially:
1 and 2 are members of the same set.
4 and 7 are members of the same set.
8 and 7 are members of the same set.


So why do you prefer the alternative solution

set1: 1 ,2
set2: 4, 8, 7 

Perhaps you had better provide a link to the original statement of the problem, not your (mis)interpretation of it.



If you are trying to construct a GRAPH, with disjoint SUBGRAPHS, then please say so.

[mnnsa]

Yes @lastchance :) thank u got it ......

[lastchance]

Confirm, please. You are trying to construct a GRAPH, and the sets are the disjoint SUBGRAPHS?

Your input pairs correspond to the connectors?

[mnnsa]

Yes it's like finding number of connected components

[lastchance]

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;

int main()
{
// ifstream in( "data.txt" );
   istringstream in( "3   \n"
                     "1 2 \n"
                     "4 7 \n"
                     "8 7 \n" );


   // Set up graph
   map<int,vector<int>> graph;
   int num_connectors;
   in >> num_connectors;
   for ( int i = 0; i < num_connectors; i++ )
   {
      int a, b;
      in >> a >> b;
      graph[a].push_back( b );
      graph[b].push_back( a );
   }


   // Build up subgraphs
   vector< set<int> > allSets;            // Sequence of subsets
   set<int> used;                         // Keeps track of all that are so far connected
   for ( auto pr : graph )
   {
      int a = pr.first;

      if ( used.insert( a ).second )      // If not connected before
      {
         set<int> subset{ a };            // New subset

         // Stack up everything still available that it is connected to and not used previously
         stack<int> connected;
         for ( int i : graph[a] ) if ( used.insert( i ).second ) connected.push( i );
   
   
         // Use the stack dynamically to expand the connected subgraph to anything not yet used
         while( !connected.empty() )        
         {
            int b = connected.top();   connected.pop();
            for ( int i : graph[b] ) if ( used.insert( i ).second ) connected.push( i );
            subset.insert( b );
         }

         // Subset is finished; add it to the sequence of subsets
         allSets.push_back( subset );
      }
   }


   // Output
   cout << "Number of subgraphs = " << allSets.size() << '\n';
   for ( int i = 0; i < allSets.size(); i++ )
   {
      cout << "Set " << i + 1 << ": ";
      for ( auto e : allSets[i] ) cout << e << " ";
      cout << '\n';
   }
}

Number of subgraphs = 2
Set 1: 1 2 
Set 2: 4 7 8