# C++ Union Find

• ``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
vector<vector<int>> roots(m, vector<int>(n, 0));
int cid = 1 /*component id*/, ans = 0;
vector<int> ufs = {0}; //union-find set
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
//only need to check left and up nb so that each nb pair is checked only once
ufs.push_back(cid);
ans++;
roots[i][j] = cid;
vector<int> nbSet;
if(i && grid[i-1][j] == '1')
nbSet.push_back(find(ufs, roots[i-1][j]));
if(j && grid[i][j-1] == '1'){
int up = find(ufs, roots[i][j-1]);
if(nbSet.empty() || nbSet[0] != up) //no need to count again for common root
nbSet.push_back(up);
}
ans -= nbSet.size(); //size could be 0, 1 or 2
cid++; //update cid to next available value
//union
if(nbSet.size()){
ufs[roots[i][j]] = nbSet[0];
if(nbSet.size() > 1)
ufs[nbSet[1]] = nbSet[0];
}
}
}
}
return ans;
}
int find(vector<int>& ufs, int i){
if(ufs[i]== i) return i;
else return ufs[i] = find(ufs, ufs[i]); //find root with path compression
}
};
``````

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