Union Find

Time Complexity

Starting from an empty data structure, any sequence of M union and find operations on N objects takes O(N + M lg* N) time.

• Proof is very difficult.

https://en.wikipedia.org/wiki/Proof\_of\_O\(log\*n\)\_time\_complexity\_of\_union%E2%80%93find

Iterative Logarithm: the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

Path Compression

It will speed up the find process because it reduce the tree height.

Recursively

public int find(int[] root, int id) {
    if(root[id]==id) return id;
    int parent = find(root, root[id]);
    root[id] = parent;
    return parent;
}

Iteratively

public int find(int[] root, int id) {
    while(root[id]!=id) {
        root[id] = root[root[id]];
        id = root[id];
    } 
    return root[id];
}

Weighting

Keep an rank[] array to count number of elements rooted under the parent. Merge the smaller tree into the larger tree.

if(rank[parent1]< rank[parent2]) {
    root[parent1] = parent2;
    rank[parent2] += rank[parent1];
} else {
    root[parent2] = parent1;
    rank[parent1] += rank[parent2];
}

Remap Matrix Cells to 1-d Parent Array

Some union find problems are set up as matrix. We can remap the matrix cell (i, j) to a unique id (just like flatten the 2d array).

id = i * n + j

We use the id itself as parent if it is itself as a set. The "-1" can be used to signal if the cell should be ignored or not.

If the matrix size is large and the #updates are just small, the overhead in initialisation is O(mn) which may more than the time required for Union-Find. In this case, we should use HashMap instead of array.

305. Number of Islands II

Archiving union-find in HashMap

Using key-value pair relationship to represent the parent-child relationship. We can use "-1" to signal no parent or assign itself as its own parent (this is the representative of the set).

The problem usually of transitive property.

737. Sentence Similarity II

class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
        if(words1.size() != words2.size()) return false;

        unordered_map<string, string> simWordsMap;
        for(pair<string, string> pair: pairs) {
            string parent1 = find(simWordsMap, pair.first);
            string parent2 = find(simWordsMap, pair.second);

            //union
            if(parent1 != parent2) simWordsMap[parent1] = parent2;
        }

        for(int i=0; i<words1.size(); i++) {
            if(words1[i] != words2[i] && find(simWordsMap, words1[i]) != find(simWordsMap, words2[i]))
                return false;
        }
        return true;

    }

    string find(unordered_map<string, string>& simWordsMap, string target) {
        if(!simWordsMap.count(target)) simWordsMap[target] = target;
        return simWordsMap[target]==target? target: find(simWordsMap,simWordsMap[target]);
    }

};