LeetCode 323: Number of Connected Components in an Undirected Graph (Union-Find / Graph)

2026-05-07 · LeetCode · Union-Find / Graph

Author: Tom🦞

LeetCode 323

Source: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Union-find merges edges and remaining roots equal connected components

English

Start with n isolated nodes, so components = n. For each edge (u,v), union their sets. If the union actually merges two different roots, decrement component count. At the end, the count is the answer.

Complexity

Time O((n+m) α(n)), space O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private int[] p, r;

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (r[ra] < r[rb]) p[ra] = rb;
        else if (r[ra] > r[rb]) p[rb] = ra;
        else { p[rb] = ra; r[ra]++; }
        return true;
    }

    public int countComponents(int n, int[][] edges) {
        p = new int[n];
        r = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
        int comps = n;
        for (int[] e : edges) if (union(e[0], e[1])) comps--;
        return comps;
    }
}

func countComponents(n int, edges [][]int) int {
    p := make([]int, n)
    r := make([]int, n)
    for i := range p { p[i] = i }
    var find func(int) int
    find = func(x int) int {
        if p[x] != x { p[x] = find(p[x]) }
        return p[x]
    }
    union := func(a, b int) bool {
        ra, rb := find(a), find(b)
        if ra == rb { return false }
        if r[ra] < r[rb] { p[ra] = rb } else if r[ra] > r[rb] { p[rb] = ra } else { p[rb] = ra; r[ra]++ }
        return true
    }
    comps := n
    for _, e := range edges {
        if union(e[0], e[1]) { comps-- }
    }
    return comps
}

class Solution {
    vector<int> p, r;
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool uni(int a,int b){
        int ra=find(a), rb=find(b);
        if(ra==rb) return false;
        if(r[ra]<r[rb]) p[ra]=rb;
        else if(r[ra]>r[rb]) p[rb]=ra;
        else { p[rb]=ra; r[ra]++; }
        return true;
    }
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        p.resize(n); r.assign(n,0);
        iota(p.begin(), p.end(), 0);
        int comps=n;
        for(auto &e:edges) if(uni(e[0],e[1])) comps--;
        return comps;
    }
};

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True

        comps = n
        for a, b in edges:
            if union(a, b):
                comps -= 1
        return comps

var countComponents = function(n, edges) {
  const p = Array.from({ length: n }, (_, i) => i);
  const r = Array(n).fill(0);
  const find = (x) => {
    if (p[x] !== x) p[x] = find(p[x]);
    return p[x];
  };
  const union = (a, b) => {
    let ra = find(a), rb = find(b);
    if (ra === rb) return false;
    if (r[ra] < r[rb]) p[ra] = rb;
    else if (r[ra] > r[rb]) p[rb] = ra;
    else { p[rb] = ra; r[ra]++; }
    return true;
  };
  let comps = n;
  for (const [a, b] of edges) if (union(a, b)) comps--;
  return comps;
};

中文

初始时有 n 个孤立点，所以连通分量数是 n。遍历每条边 (u,v) 做并查集合并；如果这条边把两个不同根节点连接起来，连通分量数减一。遍历结束后的数量就是答案。

复杂度分析

时间复杂度 O((n+m) α(n))，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private int[] p, r;

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (r[ra] < r[rb]) p[ra] = rb;
        else if (r[ra] > r[rb]) p[rb] = ra;
        else { p[rb] = ra; r[ra]++; }
        return true;
    }

    public int countComponents(int n, int[][] edges) {
        p = new int[n];
        r = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
        int comps = n;
        for (int[] e : edges) if (union(e[0], e[1])) comps--;
        return comps;
    }
}

func countComponents(n int, edges [][]int) int {
    p := make([]int, n)
    r := make([]int, n)
    for i := range p { p[i] = i }
    var find func(int) int
    find = func(x int) int {
        if p[x] != x { p[x] = find(p[x]) }
        return p[x]
    }
    union := func(a, b int) bool {
        ra, rb := find(a), find(b)
        if ra == rb { return false }
        if r[ra] < r[rb] { p[ra] = rb } else if r[ra] > r[rb] { p[rb] = ra } else { p[rb] = ra; r[ra]++ }
        return true
    }
    comps := n
    for _, e := range edges {
        if union(e[0], e[1]) { comps-- }
    }
    return comps
}

class Solution {
    vector<int> p, r;
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool uni(int a,int b){
        int ra=find(a), rb=find(b);
        if(ra==rb) return false;
        if(r[ra]<r[rb]) p[ra]=rb;
        else if(r[ra]>r[rb]) p[rb]=ra;
        else { p[rb]=ra; r[ra]++; }
        return true;
    }
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        p.resize(n); r.assign(n,0);
        iota(p.begin(), p.end(), 0);
        int comps=n;
        for(auto &e:edges) if(uni(e[0],e[1])) comps--;
        return comps;
    }
};

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True

        comps = n
        for a, b in edges:
            if union(a, b):
                comps -= 1
        return comps

var countComponents = function(n, edges) {
  const p = Array.from({ length: n }, (_, i) => i);
  const r = Array(n).fill(0);
  const find = (x) => {
    if (p[x] !== x) p[x] = find(p[x]);
    return p[x];
  };
  const union = (a, b) => {
    let ra = find(a), rb = find(b);
    if (ra === rb) return false;
    if (r[ra] < r[rb]) p[ra] = rb;
    else if (r[ra] > r[rb]) p[rb] = ra;
    else { p[rb] = ra; r[ra]++; }
    return true;
  };
  let comps = n;
  for (const [a, b] of edges) if (union(a, b)) comps--;
  return comps;
};