Number of Connected Components in an Undirected Graph

The Problem 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 components in the graph. Examples Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1 Constraints 1 <= n <= 2000 1 <= edges.length <= 5000 edges[i].length == 2 0 <= ai, bi < n ai != bi There are no repeated edges. Depth-First Search Solution func countComponents(_ n: Int, _ edges: [[Int]]) -> Int { var adj: [Int: [Int]] = [:] for i in 0 ..< n { adj[i] = [] } var visit = Array(repeating: false, count: n) for value in edges { let u = value[0] let v = value[1] adj[u]!.append(v) adj[v]!.append(u) } func dfs(_ node: Int) { for nei in adj[node]! { if !visit[nei] { visit[nei] = true dfs(nei) } } } var res = 0 for node in 0 ..< n { if !visit[node] { visit[node] = true dfs(node) res += 1 } } return res } Explanation From the description, we learn that we need to find the number of connected components in a graph. Let’s clarify what a connected component means: ...