7. Graphs — BFS, DFS and shortest paths

// BFS: shortest path in an unweighted graph (fewest hops)
int ShortestHops(Dictionary<int, List<int>> g, int start, int goal)
{
    var dist = new Dictionary<int, int> { [start] = 0 };
    var q = new Queue<int>([start]);
    while (q.Count > 0)
    {
        int u = q.Dequeue();
        if (u == goal) return dist[u];
        foreach (int v in g.GetValueOrDefault(u, []))
            if (dist.TryAdd(v, dist[u] + 1)) q.Enqueue(v);
    }
    return -1;
}

// DFS: count islands in a grid (connected components)
int Islands(char[][] grid)
{
    int count = 0;
    void Sink(int r, int c)
    {
        if (r < 0 || c < 0 || r >= grid.Length || c >= grid[0].Length || grid[r][c] != '1') return;
        grid[r][c] = '0';
        Sink(r + 1, c); Sink(r - 1, c); Sink(r, c + 1); Sink(r, c - 1);
    }
    for (int r = 0; r < grid.Length; r++)
        for (int c = 0; c < grid[0].Length; c++)
            if (grid[r][c] == '1') { count++; Sink(r, c); }
    return count;
}