# Union find find (by rank) C++ solution

• Here is my solution based on Union find by rank (http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/):

``````   int getRoot(int node, vector<int>& parent) {
if (parent[node] != node)
return parent[node] = getRoot(parent[node], parent);
return node;
}

void unionSets(int x, int y,
vector<int>& parent,
vector<int>& rank){
int xRoot = getRoot(x, parent),
yRoot = getRoot(y,parent);
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[yRoot] < rank[xRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}

vector<vector<string> > accountsMerge(vector<vector<string> >& accounts) {
int n = accounts.size();
vector<int> parents(n);
vector<int> ranks(n, 0);
for (int i = 0; i < n; ++i) parents[i] = i;

// Maps email to tree root.
map<string, int> roots;

// Union the sets.
for (int i = 0; i < n; ++i){
for (int j = 1; j < accounts[i].size(); ++j){
string& mail = accounts[i][j];
if (roots.count(mail)) {
unionSets(i, roots[mail], parents, ranks);
}
roots[mail] = getRoot(i, parents);
}
}

// Construct the sorted list of mails per user.
vector<vector<string> > res;
unordered_map<int, int> treeRootToResultIndex;
for(pair<const string, int>& i : roots) {
int accountRoot = getRoot(i.second, parents);
if (treeRootToResultIndex.count(accountRoot)) {
res[treeRootToResultIndex[accountRoot]].push_back(i.first);
} else {
treeRootToResultIndex[accountRoot] = res.size();
res.push_back(vector<string>());
vector<string>& back = res.back();
back.push_back(move(accounts[accountRoot][0]));
back.push_back(move(i.first));
}
}
return move(res);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.