2

请注意，这不是家庭作业问题。我正在对 Kattis 进行培训，我遇到了一个需要使用 Union-Find 范式的问题。鉴于问题的性质，我决定实现自己的 UnionFind 数据结构。我了解我的 DS 接口应支持：

  1. 制作集
  2. find(elem) -> 返回对该集合代表的引用
  3. merge(firstElem, secondElem) -> 合并该集合的两个父节点（同时确保它是平衡的）

现在的问题是我没有实现这个数据结构来支持整数，它通常使用一个数组来实现，其中索引是值，集合的代表总是该索引处的值。相反，我的集合包含字符串，我发现选择数据结构有困难。

4

2 回答 2

0

这是String-String union find的灵魂，可能会有所帮助。

//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;
    }
于 2019-01-23T03:12:16.943 回答
0

如果您有类似的数据String [] universal_set = {"a,b,s","d,s,w","s,d,v","m,d,s"};，请创建一个 HashMap 并获取唯一值，然后将它们分组为主集的不相交子集。

于 2018-10-23T15:17:53.367 回答