Leetcode 684: redundant connection

July 21, 2018

Introduction

It is a medium level algorithm called redundant connection. It can be solved using disjoint set data structure. I came cross the algorithm and was introduced through a mock interview more than six months ago. But I have not submitted any code on Leetcode online judge yet.

It is perfect time for me to write the code for the algorithm this Saturday.

My first practice 

Now it is 11:12 PM. I spent over 60 minutes and worked with online judge, and then wrote the code to pass all test cases.

I finally understood that the code is not easy to write using disjoint set data structure. I did a lot of learning through the those 60 minutes .

Here is C# code.

Second practice 

I read the discussion panel and one of ideas is to write union find algorithm, it takes less than 20 lines of code. I should be able to finish it in less than 20 minutes.