21. Count Connected Components in Network

Origin: Count Connected Components in Network

Given n computers labeled 0 to n-1 and a list of bidirectional communication links, find the number of connected components.

Example

Input: n = 4, links = [[0, 1], [2, 3]]

Output: 2

Explanation: 4 台电脑 0、1、2、3。链路连接 0-1 和 2-3。0 和 1 组成一组，2 和 3 组成一组，两组之间没有连接，所以有 2 个连通分量。

Input Format

• 第一行：m（链路数量）
• 第二行：n（电脑数量）
• 接下来 m 行：每行两个整数 a b，表示 a 和 b 之间有链路
• 最后一行：n

示例输入：

2
2
0 1
2 3
4

Constraints

• 1 <= n <= 1000
• 0 <= links.length <= n * (n - 1) / 2
• links[i].length == 2
• 0 <= links[i][0] < n
• 0 <= links[i][1] < n
• links[i][0] != links[i][1]（无自环）
• 每对 [a, b] 是双向的，[a, b] 和 [b, a] 被视为同一条边
• 无重复边

Output Format

返回一个整数：连通分量的数量（isolated communication groups）。

Sample Input 0

1 2
0 1
2

Sample Output 0

1

Sample Input 1

3 2
0 1
1 2
0 2
3

Sample Output 1

1

---

函数契约

// 输入：n（节点数），links（边列表，每条边 [a, b] 是双向的）
// 输出：连通分量数量（整数）
// 边界：n=1 无边 → 1；全部连通 → 1；全部不连通 → n

边界表

场景	返回什么
n=1, 无边	1
全部连通	1
全部不连通（无边）	n
正常场景	连通分量数

Resolution

我的解法

function countIsolatedCommunicationGroups(links: number[][], n: number): number {
    // 建邻接表
    const adj: Record<number, number[]> = {};
    for (let i = 0; i < n; i++) {
        adj[i] = [];
    }
    for (const [a, b] of links) {
        adj[a].push(b)
        adj[b].push(a)
    }
 
    // DFS 标记连通块
    const visited = new Set<number>();
    const dfs = (node: number) => {
        visited.add(node);
        for (const neighbor of adj[node]) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
    }
 
    // 遍历所有节点，没访问过就是新连通块
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }
 
    return count;
}

解题思路

三步走：建邻接表 → DFS 遍历连通块 → 数未访问的节点。

1. 建邻接表：遍历 links，每条边 [a,b] 加两次（adj[a].push(b) 和 adj[b].push(a)），因为边是双向的
2. DFS 函数：从当前节点出发，标记自己已访问，递归访问所有没访问过的邻居
3. 计数：遍历所有节点，没访问过说明属于新连通块，count++，然后 DFS 把整个连通块标记

复杂度

• 时间：O(n + m)，n 是节点数，m 是边数，每个节点和每条边访问一次
• 空间：O(n + m)，邻接表存 n 个节点 m 条边，visited 存 n 个节点，递归栈最深 n

测试用例

输入	输出	场景
links=[[0,1],[2,3]], n=4	2	两组各两个
links=[[0,1],[1,2]], n=3	1	全部连通
links=[], n=3	3	无边全孤立
links=[], n=1	1	单节点无边
links=[[0,1],[2,3],[4,5],[0,2]], n=6	2	两个连通块+合并

全部通过。

参考来源

• 相关题型：图论
• 相关文章：算法解题流程：从读题到提交的七步