Combine aggregate sets in C ++

Question

Starting from vector vector unsigned int ...

 vector<vector<unsigned short int> > matrix; vector<unsigned short int> row; 

I would like to combine conjugate sets (these are vectors with common elements).

To enter as input:

 matrix[0] = {0, 1, 2} matrix[1] = {1, 10} matrix[3] = {9} matrix[4] = {2, 8} matrix[5] = {7} 

as output:

 matrix[0] = {0, 1, 2, 10, 8} // it doesn't matter the order matrix[1] = {9} matrix[2] = {7} 

What is the most effective solution to this problem? Regards, Vi.

Answer 1

You can reduce this problem by searching for all connected components of the undirected graph. The vertices are your matrix rows, and the edges are non-zero. The Boost.Graph library can calculate this in O(V+E) complexity, where V is the number of vertices (matrix rows) and E number of edges (number of overlapping rows). If you don't like Boost dependency, you can use any of the available algorithms available to calculate tightly coupled components.

It remains to calculate the representation of this boundary list, which depends on whether you can sort the rows of the matrix. If you cannot sort the rows of the matrix, you can use std::find_first_of to detect nonzero overlap (which has O(N * M) complexity for 2 vectors N and M ). If you can sort them (in O(N lg N) complexity), you can use std::set_intersection to check the overlap (only O(N + M) complexity).

The output of Boost.Graph or your algorithm is a set of connected components, and then you iterate over each component and add or combine different overlapping rows of your matrix together (using std::copy or std::merge if you need to sort them).

Answer 2

I suggest you use disjoint set forest . For each set, iteratively add numbers to the set where the first number of the set belongs. After that, just print all the numbers in each of the sets. Actually, the implementation is not so complicated, but the performance will be asymptotically faster than the solution already proposed.