Understanding the Code: Connected Sum – HackerRank Solution

Understanding the Code: Connected Sum

Have you ever come across the term ‘connected sum’ in the context of graph algorithms? Wondering how it works and how it can be applied? Look no further! In this post, we will dive into the connected sum algorithm and explore its implementation in JavaScript.

What is the Connected Sum Algorithm?

The connected sum algorithm is a technique used to find connected components in a graph. It helps identify groups of nodes that are connected to each other through edges. By applying this algorithm, we can determine the size of each connected component in the graph.

Implementation in JavaScript

const MAX = 100005;
const v = new Array(MAX).fill([]);
const visited = new Array(MAX).fill(false);

// Function to calculate the size of a connected component
function getConnectedComponentSize(x) {
  const nodes = [];
  nodes.push(x);
  visited[x] = true;
  let cnt = 0;
  while (nodes.length > 0) {
    x = nodes.pop();
    cnt += 1;
    for (let y of v[x]) {
      if (!visited[y]) {
        visited[y] = true;
        nodes.push(y);
      }
    }
  }
  return cnt;
}

// Main function to calculate the connected sum
function connectedSum(graph_nodes, graph_from, graph_to) {
  for (let i = 0; i < graph_from.length; i++) {
    const x = graph_from[i];
    const y = graph_to[i];
    v[x].push(y);
    v[y].push(x);
  }

  let ans = 0;
  for (let node = 1; node <= graph_nodes; node++) {
    if (!visited[node]) {
      const cnt = getConnectedComponentSize(node);
      ans += Math.ceil(Math.sqrt(cnt));
    }
  }
  return ans;
}