# 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 componentsin 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]++;
}
}
}
}
```