# C++ Union Find Solution with union by rank and path compression

• Union Find is always used for Connected Component Labelling in image process.
Labelling connected components - Example
wiki - Disjoint-set data structure
have fun!

``````class Solution
{
public:
int numIslands(const vector<vector<char>> &grid)
{
n = grid.size();
if (n == 0)
return 0;
m = grid[0].size();

vector<vector<int>> copyGrid(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i < n + 1; i++)
for (int j = 1; j < m + 1; j++)
copyGrid[i][j] = grid[i - 1][j - 1] - '0';

onePass(copyGrid);
parent.resize(numSet + 1, 0);
nRank.resize(numSet + 1, 0);

makeSet();
int i = 0;
while (i < edge.size())
{
int u = edge[i++];
int v = edge[i++];

u = findParent(u);
v = findParent(v);
if (u != v)
{
unionSet(u, v);
numSet--;
}
}

return numSet;
}

private:
int n;
int m;
int numSet; //num of tree node
vector<int> edge;
vector<int> parent;
vector<int> nRank;
void onePass(vector<vector<int>> &copyGrid)
{
numSet = 0;
for (int i = 1; i < n + 1; i++)
for (int j = 1; j < m + 1; j++)
{
if (copyGrid[i][j] != 0)
{
if (copyGrid[i][j - 1] != 0 || copyGrid[i - 1][j] != 0)
{
if (copyGrid[i][j - 1] != 0 && copyGrid[i - 1][j] != 0)
{
copyGrid[i][j] = min(copyGrid[i][j - 1], copyGrid[i - 1][j]);
if (copyGrid[i][j - 1] != copyGrid[i - 1][j])  //find edge
{
edge.push_back(copyGrid[i - 1][j]);
edge.push_back(copyGrid[i][j - 1]);
}
}
else
copyGrid[i][j] = copyGrid[i - 1][j] == 0 ? copyGrid[i][j - 1] : copyGrid[i - 1][j];
}
else
copyGrid[i][j] = ++numSet;
}
}
}

void makeSet()
{
for (int i = 1; i < numSet + 1; i++)
parent[i] = i;
}

int findParent(int n) //path compression
{
if (parent[n] != n)
parent[n] = findParent(parent[n]);
return parent[n];
}

void unionSet(int parentX, int parentY) //union by rank
{
if (nRank[parentX] < nRank[parentY])
parent[parentX] = parentY;
else
{
parent[parentY] = parentX;
if (nRank[parentX] == nRank[parentY])
nRank[parentX]++;
}
}
};
``````

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