JavaScript union-find solution


  • 0

    With union-find algorithm, we can identify the islands by 2 steps:

    Step 1. Perform the union and find, connect the nodes by given edges
    Step 2. Count the -1 in the union find array

    const countComponents = (n, edges) => {
      const nums = Array(n).fill(-1);
    
      // Step 1. union find
      for (let i = 0; i < edges.length; i++) {
        const x = find(nums, edges[i][0]);
        const y = find(nums, edges[i][1]);
    
        // union
        if (x !== y) nums[x] = y;
      }
    
      // Step 2. count the -1
      return nums.filter(num => num === -1).length;
    };
    
    const find = (nums, i) => {
      if (nums[i] === -1) return i;
      return find(nums, nums[i]);
    };
    

Log in to reply
 

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