# Leetcode 839
https://leetcode.com/problems/similar-string-groups/description/

class UnionFindSet{
public:
    UnionFindSet(int n){
        parent = vector<int>(n);
        rank = vector<int>(n,0);
        for(int i=0;i<n;i++)
            parent[i] = i;
    }
    int Find(int x){
        if(x!=parent[x])
            parent[x] = Find(parent[x]);
        return parent[x];
    }
    bool Union(int u, int v){
        int pu = Find(u), pv = Find(v);
        if(pu==pv) return false;
        if(rank[pu]>rank[pv]) parent[pv] = pu;
        else if(rank[pv]>rank[pu]) parent[pu] = pv;
        else{
            parent[pu] = pv;
            rank[pv]++;
        }
        return true;
    }
private:
    vector<int> parent,rank;
};
class Solution {
public:
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        int len = strs[0].size();
        UnionFindSet s(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int gap = 0;
                for(int k=0;k<len;k++){
                    if(strs[i][k]!=strs[j][k])
                        gap++;
                }
                if(gap==0||gap==2)
                    s.Union(i,j);
            }
        }
        unordered_set<int> count;
        for(int i=0;i<n;i++){
            count.insert(s.Find(i));
        }
        return count.size();
    }
};