Posts

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: ...

The problem You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise. Examples Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true ...

The problem There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1] indicates that to take course 0, you have to first take course 1. Return true if you can finish all courses. Otherwise, return false. ...

The problem There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). ...

The Problem Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors: class Node { public int val; public List<Node> neighbors; } Test Case Format For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node has val == 1, the second node has val == 2, and so on. The graph is represented in the test case using an adjacency list. ...