combine pairs of integers based on common element

Question

suppose I have pair of integers for example (1,3), (5,6), (7,8), (3,9) then I want to combine this pairs into unique sets based on common element amongst them i.e. I can combine (1,3) and (3,9) because 3 is common between them, So final output for above input should be like this (1,3,9), (5,6), (7,8) One way could be to iterate through this array and based on common elements combine it and delete second pair from array which I suppose is time consuming. What is the efficient way to do this in C/C++ ?

Answer 1

One efficient way of doing this is to think of it as a graph connectivity problem. Create a graph where the nodes are the pairs of integers and add an undirected edge between two nodes if the pairs they correspond to have a common element. Now, find the connected components in this graph and construct the sets formed by the unions of the pairs that the nodes in a component correspond to.

Finding connected components takes O(E) time, which could be O(n^2) if there are n pairs. Merging them all can be done with a heap-like structure and that would take O(log n) per insertion. Thus the runtime is O(E + n log n) which is at most O(n^2). The complexity could be much lower depending on how many of the pairs have elements in common.

Answer 2

I'd use a map from int to shared_ptr<list<int>>, list over vector due to this being a good use-case for splice:

class Combiner {
    std::unordered_map<int, std::shared_ptr<std::list<int>>> map;

public:
    void addPair(const std::pair<int, int>& p) {
        auto a = map.find(p.first);
        auto b = map.find(p.second);

        // 4 cases: (1) both found the same list, (2) both found different lists,
        //          (3) one found a list, (4) neither found a list

        if (a != map.end()) {
            if (b != map.end()) {
                if (a->second == b->second) {
                    // (1) nothing to do, done
                }
                else {
                    // (2) have to combine our lists
                    a->second->splice(a->second.end(), *(b->second));
                    b->second = a->second;
                }
            }
            else {
                // (3), add p.second to a
                a->second->push_back(p.second);
                map.insert(std::make_pair(p.second, a->second));
            }
        }
        else {
            if (b != map.end()) {
                // (3), add p.first to b
                b->second->push_back(p.first);
                map.insert(std::make_pair(p.first, b->second));
            }
            else {
                // (4), make a new list
                auto new_list = std::make_shared<std::list<int>>();
                new_list->push_back(p.first);
                new_list->push_back(p.second);
                map.insert(std::make_pair(p.first, new_list));
                map.insert(std::make_pair(p.second, new_list));
            }
        }
    }

Answer 3

What types do you want for the containers? Are they sets?

#include <algorithm>
#include <set>
#include <list>
#include <iostream>

void dump( const std::string & label, const std::list< std::set< int > > & values )
{
    std::cout << label << std::endl;
    for( auto iter : values )
    {
        std::cout << "{ ";
        for( auto val : iter )
            std::cout << val << ", ";
        std::cout << "}, ";
    }
    std::cout << std::endl;
}

void combine( std::list< std::set< int > > & values )
{
    for( std::list< std::set< int > >::iterator iter = values.begin(); iter != values.end(); ++iter )
        for( std::list< std::set< int > >::iterator niter( iter ); ++niter != values.end(); )
            if( std::find_first_of( iter->begin(), iter->end(), niter->begin(), niter->end() ) != iter->end() )
            {
                iter->insert( niter->begin(), niter->end() );
                values.erase( niter );
                niter = iter;
            }
}

int main( int argc, char ** argv )
{
    std::list< std::set< int > > to_process = { { 1, 3 }, { 5, 6 }, { 7, 8 }, { 3, 9 } };
    dump( "Before", to_process );
    combine( to_process );
    dump( "After", to_process );

    to_process = { { 1, 3 }, { 5, 6 }, { 7, 8 }, { 3, 9 }, { 9, 13 }, { 8, 11 } };
    dump( "Before", to_process );
    combine( to_process );
    dump( "After", to_process );

    to_process = { { 1, 2 }, { 5, 6 }, { 7, 8 }, { 3, 9 }, { 9, 13 }, { 8, 13 } };
    dump( "Before", to_process );
    combine( to_process );
    dump( "After", to_process );

    return 0;
}

Output:

Before
{ 1, 3, }, { 5, 6, }, { 7, 8, }, { 3, 9, }, 
After
{ 1, 3, 9, }, { 5, 6, }, { 7, 8, }, 
Before
{ 1, 3, }, { 5, 6, }, { 7, 8, }, { 3, 9, }, { 9, 13, }, { 8, 11, }, 
After
{ 1, 3, 9, 13, }, { 5, 6, }, { 7, 8, 11, }, 
Before
{ 1, 2, }, { 5, 6, }, { 7, 8, }, { 3, 9, }, { 9, 13, }, { 8, 13, }, 
After
{ 1, 2, }, { 5, 6, }, { 3, 7, 8, 9, 13, },