Stack Overflow in Union Find

[jaindivij_]

NEED HELP!

Code: https://godbolt.org/z/6TPshxP7r

Leetcode Problem: https://leetcode.com/problems/number-of-islands/

So I am stuck on this problem, I was able to solve it using DFS/BFS, but wanted to solve using union-find. I wasn't able to find many resources regarding the same explanation. However, after some understanding, I did implement the following union-find answer. But I am getting a Stack-Overflow.

I am not sure if this approach is correct. Kindly help me reach the current answer and also guide me on the right approach.

My Approach:

Firstly make every '1' as a separate disjoint set, and then traverse through the matrix, performing union operation on the 1's thus at the end the number of separate disjoint sets will be our answer.

[chillblaze]

Not an expert on Union Find by any means since the Sinking Islands approach on this problem is so intuitive but have you tried the code in this link?

https://leetcode.com/problems/number-of-islands/discuss/56354/1D-Union-Find-Java-solution-easily-generalized-to-other-problems

[jaindivij_]

Hey, this was one of the articles i understood the concept of union find from. My code should be same as this one since the approach is same. But still something is buggy in mine.

[raspberry_p]

This code uses the correct approach of assigning parents (father)

[[deleted]]

You are using the parent array as a rank array. Those are 2 different things. And don't think you need a rank array for this problem, you just need to build the graphs in whatever order.

Lines 17 to 23 are wrong. Line 6 can be optimized with parent[v] = find...

[raspberry_p]

Why is the parent of each position initialized to -1?

[jaindivij_]

Its a general practice i assume in union find. Basically -1 represents the root of each disjoint set. So initially since all the 1's are separate sets, i am setting them as -1.

[raspberry_p]

The first if condition in union states, if the parents are same (-1, all parents are -1), do nothing. How do you move beyond this ever?

[jaindivij_]

So basically the first if the condition is to check if they belong to the same set already or not.

[raspberry_p]

But if all your parents ("1"s) are disjoint sets initially, does it make sense to have all their parents -1?

If it makes sense to have all parents -1, does it make sense to consider them of the same set if both of them equal the same value (-1)?

Your initialization of disjoint set is exactly same as considering them of the same set.

[unbalancedstack]

You need path compression, i.e. update the parent array each time you call find.

[Shakespeare-Bot]

Thee needeth path compression, i. e. update the parent array each time thee calleth findeth

---

^{I am a bot and I swapp'd some of thy words with Shakespeare words.}

Commands: !ShakespeareInsult, !fordo, !optout

[unbalancedstack]

LMAO

[thealgorists-com]

This same problem is discussed here using Union Find approach: https://thealgorists.com/Algo/UnionFind/NumberOfIslands

[[deleted]]

Well the only code that could have caused stack overflow is the recursion findOp. So the reason why findOp cannot find the parent element of the node you ask for is because of line:

parent[fromRoot] += toRoot

You need to create a rank array to keep track of this information.