LeetCode 第323题：无向图中连通分量的数目

📖 文章摘要

本文详细解析LeetCode第323题“无向图中连通分量的数目”，这是一道图论中并查集的经典问题。文章提供了并查集和DFS两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升图论算法能力的程序员。

核心知识点： 并查集、深度优先搜索、图论
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升图论算法能力的程序员

题目描述

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例

示例 1：

输入: n = 5, edges = [[0,1], [1,2], [3,4]]
输出: 2

示例 2：

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出: 1

提示

1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
edges 中不会出现重复的边

解题思路

方法一：并查集

使用并查集数据结构来解决连通分量的问题。

关键点：

初始化每个节点的父节点为自身
实现查找和合并操作
通过路径压缩优化查找
最后统计不同父节点的数量

具体步骤：

初始化并查集数组
遍历所有边，合并相连的节点
统计不同父节点的数量
返回连通分量的数目

时间复杂度：O(N + MlogN)，其中N是节点数，M是边数空间复杂度：O(N)

方法二：DFS

使用深度优先搜索遍历图，统计连通分量。

关键点：

构建邻接表表示图
使用visited数组标记访问过的节点
每次DFS遍历一个连通分量
统计DFS调用次数

具体步骤：

构建邻接表
初始化visited数组
遍历所有节点，对未访问的节点进行DFS
统计DFS的调用次数

时间复杂度：O(N + M) 空间复杂度：O(N + M)

图解思路

并查集过程分析表

步骤	操作	父节点数组	连通分量数
初始	初始化	[0,1,2,3,4]	5
1	合并(0,1)	[0,0,2,3,4]	4
2	合并(1,2)	[0,0,0,3,4]	3
3	合并(3,4)	[0,0,0,3,3]	2

DFS遍历过程表

起始节点	访问顺序	已访问节点	连通分量数
0	0->1->2	[0,1,2]	1
3	3->4	[0,1,2,3,4]	2

代码实现

C# 实现

public class Solution {
    private int[] parent;
    
    public int CountComponents(int n, int[][] edges) {
        parent = new int[n];
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 合并相连的节点
        foreach (var edge in edges) {
            Union(edge[0], edge[1]);
        }
        
        // 统计连通分量
        HashSet<int> components = new HashSet<int>();
        for (int i = 0; i < n; i++) {
            components.Add(Find(i));
        }
        
        return components.Count;
    }
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    private void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}

Python 实现

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # 路径压缩
            return parent[x]
        
        def union(x, y):
            parent[find(x)] = find(y)
        
        # 初始化并查集
        parent = list(range(n))
        
        # 合并相连的节点
        for x, y in edges:
            union(x, y)
        
        # 统计连通分量
        return len({find(i) for i in range(n)})

C++ 实现

class Solution {
private:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
    
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        // 初始化并查集
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 合并相连的节点
        for (const auto& edge : edges) {
            unite(edge[0], edge[1]);
        }
        
        // 统计连通分量
        unordered_set<int> components;
        for (int i = 0; i < n; i++) {
            components.insert(find(i));
        }
        
        return components.size();
    }
};

执行结果

C# 实现

执行用时：108 ms
内存消耗：40.8 MB

Python 实现

执行用时：92 ms
内存消耗：15.8 MB

C++ 实现

执行用时：12 ms
内存消耗：12.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	108 ms	40.8 MB	实现简洁，性能适中
Python	92 ms	15.8 MB	代码最简洁
C++	12 ms	12.4 MB	性能最优

代码亮点

🎯 使用并查集高效解决连通性问题
💡 通过路径压缩优化查找操作
🔍 使用HashSet去重统计连通分量
🎨 代码结构清晰，变量命名规范

常见错误分析

🚫 忘记路径压缩优化
🚫 并查集初始化错误
🚫 合并操作实现不当
🚫 统计连通分量时重复计数

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
并查集	O(N + MlogN)	O(N)	实现简单，效率高	需要额外空间
DFS	O(N + M)	O(N + M)	思路直观	需要构建邻接表

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第323题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法一：并查集

方法二：DFS

图解思路

并查集过程分析表

DFS遍历过程表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流