Merge слитной наборы в C++

Question

Начиная от вектора вектора unsigned int ...

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

Я хотел бы объединить слитные наборы (которые являются векторами с общими элементами).

, для примера, в качестве входных данных:

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

в качестве вывода:

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

Что является наиболее эффективным решением этой проблемы? С уважением, Vi.

Answer 1

Вы можете уменьшить эту проблему до , нахожу все связанные компоненты неориентированного графа. Вершины являются вашими матричными строками, а ребра отличны от нуля. Библиотека Boost.Graph может вычислить это в O(V+E) сложности, где V - это число вершин (строк матрицы) и E количество ребер (количество перекрывающихся строк). Если вам не нравится зависимость от Boost, вы можете использовать любой из available algorithms для вычисления сильно связанных компонентов.

Что остается, так это вычислить представление этого краевого списка, которое зависит от того, можете ли вы сортировать строки матрицы. Если вы не можете сортировать строки матрицы, вы можете использовать std::find_first_of для обнаружения ненулевого перекрытия (который имеет O(N * M) сложность для 2 векторов N и M элементов). Если вы можете сортировать их (в сложности O(N lg N)), вы можете использовать std::set_intersection для проверки наложения (только O(N + M) сложности).

Выход Boost.Graph или ваш алгоритм является набором связных компонент, а затем вы цикл по каждому компоненту и добавить или объединить различные пересекающиеся ряды вашей матрицы вместе (с использованием std::copy или std::merge если вам нужно отсортирован).

Answer 2

Предлагаю вам использовать disjoint set forest. Для каждого набора итеративно добавьте числа в набор, где принадлежит первое число набора. После этого просто распечатайте все числа в каждом из наборов. На самом деле реализация не так уж и трудна, но производительность будет асимптотически быстрее, чем реализация уже предложенного решения.