# Javascript: Connected Graph Components (2021)

Prompt

You have a graph of n nodes.

You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Questions

• What constitutes a connected component?

Insights

• We can unite common/valid groups into components using a disjoint set data structure.
• Once we've done this, we simply need to count the number of unique root nodes (`self-parent`) across our groups.

Approach

• Define a component counter (`components`).
• Create a disjoint set with `n` nodes.
• Unify disjoint components using `edges`.
• If we find a node that is its own parent, this signifies the root of a unique component.
• In this case, add to `components` counter.
• Return `components` count.

Complexity

``````Time: O(n^3)
Space: O(n)
``````

## Solution

``````/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/

var countComponents = function(n, edges) {
// Define component count
let components = 0;

// Define a disjoint set with size (n)
const uf = new UnionFind(n);

// For all connections, unite elements in disjoint set
for (const [x, y] of edges) uf.union(x, y);

// Compute number of nodes with parent as self (indicates a unique component once edges are united)
for (let i = 0; i < n; i++) {
if (i === uf.find(i)) components++;
}

// Return component count
return components;
};

class UnionFind {
constructor(size) {
this.root = Array(size).fill().map((_, i) => i);
this.rank = Array(size).fill().map((_) => 1);
}

find(x) {
if (x === this.root[x]) return x;
this.root[x] = this.find(this.root[x]);
return this.root[x];
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.root[rootX] < this.root[rootY]) {
this.root[rootX] = rootY;
} else if (this.root[rootX] > this.root[rootY]) {
this.root[rootY] = rootX;
} else {
this.root[rootY] = rootX;
this.rank[rootX]++;
}
}
}
}
``````