Skip to content
DSA graphs 12 min read

Graph Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the graph exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Number of Islands

Idea: Treat the grid as a graph where each land cell connects to its 4 neighbors. Scan every cell; when you hit unvisited land, increment the count and flood-fill (DFS/BFS) the whole island, sinking it to water so it isn’t counted again. This is connected components on a grid.

Complexity: O(m·n) time, O(m·n) worst-case space (recursion / queue).

int numIslands(std::vector<std::vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), count = 0;
    std::function<void(int,int)> dfs = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != '1') return;
        grid[r][c] = '0';                       // sink
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (grid[r][c] == '1') { count++; dfs(r, c); }
    return count;
}

Pitfall: Forgetting to mark cells visited (sinking to '0') causes infinite recursion or massive overcounting. If you can’t mutate the grid, keep a separate visited matrix.

Q2. Flood Fill

Idea: A straightforward DFS/BFS from the start pixel, spreading to 4-directional neighbors that share the original color. Capture the start color first, and bail out immediately if it already equals the new color (otherwise you loop forever).

Complexity: O(m·n) time, O(m·n) space worst case.

std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& img,
                                        int sr, int sc, int newColor) {
    int old = img[sr][sc];
    if (old == newColor) return img;
    int m = img.size(), n = img[0].size();
    std::function<void(int,int)> dfs = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= m || c >= n || img[r][c] != old) return;
        img[r][c] = newColor;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
    dfs(sr, sc);
    return img;
}

Pitfall: Skipping the old == newColor early return makes the recursion never terminate, because repainted cells still match the fill condition.

Q3. Clone Graph

Idea: DFS (or BFS) while keeping a hash map from original node → its clone. Create a clone the first time you see a node, then recurse to clone and wire up its neighbors. The map both stores results and breaks cycles — if a node is already in the map, return its existing clone.

Complexity: O(V + E) time, O(V) space.

// struct Node { int val; vector<Node*> neighbors; };
Node* cloneGraph(Node* node, std::unordered_map<Node*, Node*>& seen) {
    if (!node) return nullptr;
    if (seen.count(node)) return seen[node];
    Node* copy = new Node(node->val);
    seen[node] = copy;                          // record before recursing
    for (Node* nb : node->neighbors)
        copy->neighbors.push_back(cloneGraph(nb, seen));
    return copy;
}

Pitfall: Insert the clone into the map before recursing into neighbors. If you recurse first, a cycle leads you back to an unrecorded node and you spin forever creating duplicate clones.

Q4. Course Schedule

Idea: Build a directed graph b → a for each prerequisite [a, b]. You can finish all courses iff the graph is a DAG (no cycle). Kahn’s topological sort is the cleanest test: if you can process all numCourses vertices by repeatedly removing in-degree-0 nodes, there’s no cycle.

Complexity: O(V + E) time, O(V + E) space.

bool canFinish(int numCourses, std::vector<std::vector<int>>& prereq) {
    std::vector<std::vector<int>> adj(numCourses);
    std::vector<int> indeg(numCourses, 0);
    for (auto& p : prereq) { adj[p[1]].push_back(p[0]); indeg[p[0]]++; }
    std::queue<int> q;
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
    int done = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); done++;
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    return done == numCourses;
}

Pitfall: Get the edge direction right. Prerequisite [a, b] means “b before a,” so the edge is b → a and you increment the in-degree of a. Reversing it silently passes some tests and fails others.

Q5. Word Ladder

Idea: Model each word as a vertex with edges to words that differ by one letter; the answer is the shortest path from beginWord to endWord, so use BFS. Generate neighbors by trying every position × every letter a–z and keeping only words still in the unused set. Removing words from the set as you enqueue them keeps each visited once.

Complexity: O(N · L · 26) time where N = number of words, L = word length; O(N · L) space.

int ladderLength(std::string begin, std::string end,
                 std::vector<std::string>& wordList) {
    std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
    if (!dict.count(end)) return 0;
    std::queue<std::string> q; q.push(begin);
    int steps = 1;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            std::string w = q.front(); q.pop();
            if (w == end) return steps;
            for (int p = 0; p < (int)w.size(); p++) {
                char orig = w[p];
                for (char c = 'a'; c <= 'z'; c++) {
                    w[p] = c;
                    if (dict.count(w)) { dict.erase(w); q.push(w); }
                }
                w[p] = orig;
            }
        }
        steps++;
    }
    return 0;
}

Pitfall: Counting edges instead of words. The transformation length counts the words in the sequence (including both endpoints), so start steps at 1, not 0.

Q6. Network Delay Time

Idea: Single-source shortest path from k, then the answer is the maximum shortest distance (the last node to hear the signal). Use Dijkstra with a min-heap. If any node is still unreachable (distance infinite), return -1.

Complexity: O((V + E) log V) time, O(V + E) space.

int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
    std::vector<std::vector<std::pair<int,int>>> g(n + 1);
    for (auto& t : times) g[t[0]].push_back({t[1], t[2]});
    std::vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;
    std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>,
                        std::greater<>> pq;
    pq.push({0, k});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) return -1;
        ans = std::max(ans, dist[i]);
    }
    return ans;
}

Pitfall: Nodes are labeled 1..n, so size your arrays n + 1 and ignore index 0. Also remember to return -1 when any node stays unreachable — taking the max alone would wrongly return infinity.

Q7. Cheapest Flights Within K Stops

Idea: A bounded version of Bellman-Ford: run exactly k + 1 relaxation rounds (at most k stops means at most k + 1 edges). Crucially, relax from a snapshot of distances each round so a single round can’t chain multiple flights together.

Complexity: O(k · E) time, O(V) space.

int findCheapestPrice(int n, std::vector<std::vector<int>>& flights,
                      int src, int dst, int k) {
    const int INF = 1e9;
    std::vector<int> dist(n, INF);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {                 // k+1 rounds
        std::vector<int> tmp = dist;               // snapshot
        for (auto& f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (dist[u] != INF && dist[u] + w < tmp[v])
                tmp[v] = dist[u] + w;
        }
        dist = tmp;
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

Pitfall: Relaxing in place (without the per-round snapshot) lets one round take several flights at once, so you’d allow more than k stops. Always relax from the previous round’s distances.

That’s the full answer sheet. Back to the graph exercises or continue to greedy algorithms.

Last updated June 25, 2026
Was this helpful?