Intuition

Start with n isolated components. Each edge that joins two different components reduces the count by one — that is exactly what union-find tracks.

Approach

Initialize a DSU with each node its own parent and a component count of n.
For each edge, union the endpoints; if they were in different sets, decrement the count.
Return the final count.

Complexity

Time — O((V+E) alpha): near-constant union-find operations.
Space — O(V): the parent array.

Full Solution — all languages

class Solution:
    def countComponents(self, n, edges):
        par=list(range(n))
        def find(x):
            while par[x]!=x:
                par[x]=par[par[x]]; x=par[x]
            return x
        comp=n
        for a,b in edges:
            ra,rb=find(a),find(b)
            if ra!=rb: par[ra]=rb; comp-=1
        return comp

import java.util.*;

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] par=new int[n]; for(int i=0;i<n;i++)par[i]=i; int comp=n; for(int[] e:edges){int ra=find(par,e[0]),rb=find(par,e[1]); if(ra!=rb){par[ra]=rb;comp--;}} return comp;
    }
    int find(int[] par,int x){while(par[x]!=x){par[x]=par[par[x]];x=par[x];}return x;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> par(n); for(int i=0;i<n;i++)par[i]=i; function<int(int)> find=[&](int x){while(par[x]!=x){par[x]=par[par[x]];x=par[x];}return x;}; int comp=n; for(auto& e:edges){int ra=find(e[0]),rb=find(e[1]); if(ra!=rb){par[ra]=rb;comp--;}} return comp;
    }
};

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function(n, edges) {
    const par=[]; for(let i=0;i<n;i++)par[i]=i; function find(x){while(par[x]!==x){par[x]=par[par[x]];x=par[x];}return x;} let comp=n; for(const e of edges){const ra=find(e[0]),rb=find(e[1]); if(ra!==rb){par[ra]=rb;comp--;}} return comp;
};

Number of Connected Components in an Undirected Graph

Example 1

Example 2

Constraints