Introduction
It is my study time to go over those union find algorithm from top ranking 100 to 200 in weekly contest 112 on Leetcode.com. I like to write a case study on my learning of player 176.
Case study
I chose to write a C# code based on player ranking 176. I wrote C# code but I found out the code could not pass online judge.
It is good thing since I can learn how to trouble shooting the problem. I could not pinpoint the bug, so I continued to study more about union find algorithm.
After more than one hour study, I found the bug. I submitted the code, here is my C# code.
I also learned how to write a path compression function using iterative solution. I learned from the website of lecture note.
Iterative way path compression
Buggy code
It took me more than one hour to find the bug. I spent time to write down each step of union, and then figure out why there are two trees in test case 1. One of reasons is that Parent member should be private, so that it can not be accessed directly, only available for function Find.
Rule No. 1
Only work on root of tree in union find. Connect one root as another root's child. Do not confuse the parent node with root node.
No comments:
Post a Comment