Какую структуру данных использовать для реализации непересекающихся множеств (union find)?

#java #data-structures #union-find

#java #структуры данных #объединение-поиск

Вопрос:

Пожалуйста, обратите внимание, что это не вопрос домашнего задания. Я тренируюсь на Kattis, и у меня возник вопрос, который требует использования парадигм Union-Find. Учитывая характер проблемы, я решил реализовать свою собственную структуру данных UnionFind. Я понимаю, что интерфейс моего DS должен поддерживать:

MakeSet
find(elem) -> возвращает ссылку на представителя этого набора
слияние (firstElem, secondElem) -> объединяет два родительских элемента этого набора (также гарантирует, что он сбалансирован)

Теперь проблема в том, что я не реализую эту структуру данных для поддержки целых чисел, которая обычно реализуется с использованием массива, где индексом является значение, а представителем набора всегда является значение по этому индексу. Вместо этого мой набор содержит строки, и я испытываю трудности с выбором структуры данных.

1. utmost parent of that set … наборы представляют собой неупорядоченные коллекции. Что является предельным родителем?

2. О, я имел в виду представителя этого набора. Я неправильно сформулировал это — я отредактирую.

3. Ваш вопрос неясен. Пожалуйста, объясните, что вы подразумеваете под «представителем набора».

4. Map<String, String> .

Ответ №1:

если у вас есть такие данные String [] universal_set = {"a,b,s","d,s,w","s,d,v","m,d,s"}; , создайте HashMap и получите уникальные значения, затем сгруппируйте их как непересекающийся подмножество основного набора.

Ответ №2:

Вот soultion для поиска объединения строк-String, который может помочь.

 //set all pairs
for(String[] pair : pairs){
            String parent0 = find(pair[0], map);
            String parent1 = find(pair[1], map);
            if(!parent0.equals(parent1)) map.put(parent0, parent1);
        }
//check if two string are same group
find(words1[i], map).equals(find(words2[i], map)

//find 
private String find(String word, Map<String, String> map){
        if(!map.containsKey(word)) return word;
        String str = word;
        while(map.containsKey(str)){
            str = map.get(str);
        }
        map.put(word, str);
        return str;
    }