Redundant Connection

• The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

I think `MAX_EDGE_VAL` should be `1000`?

• @jwgoh Thank you, it has been corrected.

• When do we update the rank? Thx.

• We choose the leader that has a lower following to pick up a new follower.

Other way around right? The root of the shorter tree is attached to the root of the bigger tree

• @dylan20 Corrected, thanks.

• we can use just map/unordered_map to find id of each edge fast in input array, and find cycle in (N+M) (DFS) after that find in O(N) max of indexes. So, first solution + maps should work total in O(N) or O(NlogN).

• @awice I am not sure if the sentence `Specifically, the meaning of rank is that there are less than 2 ^ rank[x] followers of x` is true. Say, for example, we run the following, right after initializing DSU: `for(int i=2; i<1000 ; i++) { union(1,i); }`. `rank[1]` will always be 1 after the first call to union, but after the for loop, 1 will have 998 followers.

• If you do it by rank, it is not alph(n) time, it is log(n) time. You gotta do it by path compression in order to approximate constant time.

• @BinGeGE Using both approximates constant. See link.

• in second approach, how does this requirement is ensured? `If there are multiple answers, return the answer that occurs last in the given 2D-array`

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