Redundant Connection

  • 0

    Click here to see the full article post

  • 0

    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?

  • 0

    @jwgoh Thank you, it has been corrected.

  • 0

    When do we update the rank? Thx.

  • 0

    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

  • 0

    @dylan20 Corrected, thanks.

  • 0

    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).

  • 0

    @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.

Log in to reply

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