7. Graphs (Days 90—104)

Number of Islands (DFS)

def numIslands(grid):
    if not grid: return 0
    count = 0
    m, n = len(grid), len(grid[0])

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i+1, j); dfs(i-1, j)
        dfs(i, j+1); dfs(i, j-1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

Clone Graph (BFS)

// Java — BFS with HashMap
public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();
    Queue<Node> q = new LinkedList<>();
    map.put(node, new Node(node.val));
    q.offer(node);
    while (!q.isEmpty()) {
        Node curr = q.poll();
        for (Node nei : curr.neighbors) {
            if (!map.containsKey(nei)) {
                map.put(nei, new Node(nei.val));
                q.offer(nei);
            }
            map.get(curr).neighbors.add(map.get(nei));
        }
    }
    return map.get(node);
}

More Problems