Interview Guide: Graphs Problems and Solutions

Graph Problems in Technical Interviews: A Complete Guide

Graphs are one of the most frequently tested data structures in technical interviews. Unlike arrays or linked lists, graphs require you to model relationships between entities, making them ideal for assessing a candidate's ability to think in terms of connections, traversals, and real-world abstractions. This guide covers everything you need to know to confidently handle graph problems in your next coding interview.

What Are Graph Problems?

In the context of technical interviews, a graph problem is any coding challenge that involves a collection of nodes (vertices) connected by edges. These problems test your ability to represent, traverse, and manipulate graph structures efficiently. Common graph problem categories include:

• Traversal problems — exploring all nodes (BFS, DFS)
• Pathfinding problems — finding shortest or specific paths between nodes
• Connectivity problems — determining if nodes are connected, counting connected components
• Cycle detection — identifying cycles in directed or undirected graphs
• Topological ordering — ordering nodes based on dependencies
• Graph construction — building a graph from given data and solving a problem on it

Why Graph Problems Matter in Interviews

Interviewers love graph problems for several compelling reasons:

• They reveal algorithmic thinking. Graphs force you to reason about non-linear data structures, which separates strong candidates from those who only memorize array manipulation tricks.
• They test breadth of knowledge. A single graph problem can touch BFS, DFS, Dijkstra's algorithm, union-find, topological sort, and dynamic programming, allowing interviewers to probe multiple areas in one question.
• They map to real-world systems. Social networks, web crawlers, dependency resolvers, GPS navigation, and circuit design all use graphs. Demonstrating graph proficiency signals you can build real software.
• They expose communication skills. Explaining traversal choices, time-space tradeoffs, and edge cases requires clear technical communication.

Graph Fundamentals You Must Know

Graph Representations

The two primary ways to represent a graph in code are the adjacency list and the adjacency matrix. For interviews, the adjacency list is almost always preferred due to its space efficiency and natural fit for traversal algorithms.

Adjacency List (Recommended for most problems):

# Undirected graph represented as adjacency list using dictionary
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Alternative using list of lists (for 0-indexed integer nodes)
# graph[i] contains neighbors of node i
n = 6  # number of nodes
graph = [[] for _ in range(n)]
graph[0] = [1, 2]      # edges from node 0
graph[1] = [0, 3, 4]   # edges from node 1
graph[2] = [0, 5]      # edges from node 2
graph[3] = [1]         # edges from node 3
graph[4] = [1, 5]      # edges from node 4
graph[5] = [2, 4]      # edges from node 5

Adjacency Matrix (Use for dense graphs or when edge weights need O(1) lookup):

# Adjacency matrix for a weighted directed graph
# matrix[i][j] = weight, or 0/float('inf') if no edge
INF = float('inf')
n = 4
matrix = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]

Edge List Representation

Sometimes problems provide input as an edge list, which is useful for algorithms like Kruskal's Minimum Spanning Tree or Union-Find:

# edges = [(u, v, weight), ...]
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 2),
    (2, 3, 5)
]

Core Graph Algorithms

1. Depth-First Search (DFS)

DFS explores as far down a branch as possible before backtracking. It's ideal for problems involving path existence, connected components, cycle detection, and topological sorting. DFS can be implemented recursively (cleaner for interviews) or iteratively with a stack.

Problem: Find all connected components in an undirected graph.

def count_connected_components(n, edges):
    """
    Given n nodes (0 to n-1) and an edge list,
    return the number of connected components.
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False] * n
    components = 0
    
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
    
    for i in range(n):
        if not visited[i]:
            components += 1
            dfs(i)
    
    return components

# Example usage
edges = [(0, 1), (1, 2), (3, 4)]
print(count_connected_components(5, edges))  # Output: 2 (component 0-1-2 and 3-4)

2. Breadth-First Search (BFS)

BFS explores level by level using a queue. It finds shortest paths in unweighted graphs and is excellent for problems involving "minimum steps," "nearest exit," or "level-order" requirements.

Problem: Shortest path in an unweighted graph from source to target.

from collections import deque

def shortest_path_unweighted(n, edges, source, target):
    """
    Returns the minimum number of edges from source to target.
    Returns -1 if no path exists.
    """
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    queue = deque([source])
    visited = [False] * n
    distance = [-1] * n
    
    visited[source] = True
    distance[source] = 0
    
    while queue:
        node = queue.popleft()
        if node == target:
            return distance[node]
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    
    return -1

# Example
edges = [(0, 1), (1, 2), (2, 3), (0, 3)]
print(shortest_path_unweighted(4, edges, 0, 3))  # Output: 1 (direct edge 0-3)

3. Topological Sort

Topological sort orders nodes in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, u comes before v. Use cases include build systems, course prerequisites, and dependency resolution. Two approaches: DFS-based and Kahn's algorithm (BFS-based using in-degree).

Problem: Determine if all courses can be completed given prerequisites (LeetCode 207: Course Schedule).

from collections import deque

def can_finish_courses(num_courses, prerequisites):
    """
    Returns True if it's possible to finish all courses
    without cyclic dependencies.
    prerequisites[i] = [course, prerequisite] meaning
    prerequisite -> course
    """
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    
    # Build graph and in-degree array
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Kahn's algorithm: start with all 0 in-degree nodes
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    courses_taken = 0
    
    while queue:
        node = queue.popleft()
        courses_taken += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return courses_taken == num_courses

# Example: 4 courses, prereqs: 1->0, 2->1, 3->2 (no cycle)
prereqs = [[0, 1], [1, 2], [2, 3]]
print(can_finish_courses(4, prereqs))  # Output: True

4. Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue to always expand the node with the smallest known distance. This is a staple for pathfinding in maps, network routing, and game AI.

Problem: Find the minimum cost to travel from node 0 to node n-1 in a weighted directed graph.

import heapq

def dijkstra_shortest_path(n, edges, source):
    """
    edges: list of (u, v, weight) for directed edges
    Returns shortest distance from source to all nodes.
    """
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    
    distances = [float('inf')] * n
    distances[source] = 0
    heap = [(0, source)]  # (distance, node)
    
    while heap:
        current_dist, node = heapq.heappop(heap)
        
        # Skip if we've found a better path already
        if current_dist > distances[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return distances

# Example: directed edges with weights
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
distances = dijkstra_shortest_path(4, edges, 0)
print(distances)  # Output: [0, 3, 1, 4]  (0->2->1->3 costs 1+2+1=4)

5. Bellman-Ford Algorithm

When graphs may contain negative edge weights (but no negative cycles that are reachable), Bellman-Ford is the algorithm of choice. It relaxes all edges V-1 times and can detect negative cycles. It's slower than Dijkstra but more versatile.

def bellman_ford(n, edges, source):
    """
    edges: list of (u, v, weight)
    Returns distances and whether a negative cycle exists.
    Handles negative weights but not negative cycles reachable from source.
    """
    distances = [float('inf')] * n
    distances[source] = 0
    
    # Relax edges n-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
                updated = True
        if not updated:
            break  # early termination if no updates
    
    # Check for negative cycles (one more relaxation)
    for u, v, w in edges:
        if distances[u] != float('inf') and distances[u] + w < distances[v]:
            return distances, True  # negative cycle detected
    
    return distances, False

# Example with a negative weight edge (but no negative cycle)
edges = [(0, 1, 4), (0, 2, 3), (1, 3, -2), (2, 1, 1), (2, 3, 5)]
distances, has_negative_cycle = bellman_ford(4, edges, 0)
print(distances)           # Output: [0, 4, 3, 2]
print(has_negative_cycle)  # Output: False

6. Union-Find (Disjoint Set Union)

Union-Find is not a graph traversal algorithm but a data structure that tracks disjoint sets. It's exceptionally efficient for connectivity queries, cycle detection in undirected graphs, and Kruskal's MST algorithm. It uses union by rank and path compression for near-constant time operations.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        # Path compression: point directly to root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # already in same set (cycle detected)
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True  # successfully united

# Problem: Detect cycle in an undirected graph
def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return True  # edge connects two nodes already in same set
    return False

edges_with_cycle = [(0, 1), (1, 2), (2, 0)]
print(has_cycle(3, edges_with_cycle))  # Output: True

7. Minimum Spanning Tree (MST)

An MST connects all nodes with minimum total edge weight. Two classic algorithms: Kruskal's (uses Union-Find, great for sparse graphs) and Prim's (uses a priority queue, great for dense graphs).

Kruskal's Algorithm:

def kruskal_mst(n, edges):
    """
    edges: list of (u, v, weight)
    Returns the total weight of the MST and the MST edges.
    """
    uf = UnionFind(n)
    # Sort edges by weight (greedy approach)
    sorted_edges = sorted(edges, key=lambda e: e[2])
    
    mst_edges = []
    total_weight = 0
    
    for u, v, w in sorted_edges:
        if uf.union(u, v):
            mst_edges.append((u, v, w))
            total_weight += w
            # Early exit: MST has n-1 edges
            if len(mst_edges) == n - 1:
                break
    
    return total_weight, mst_edges

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
weight, mst = kruskal_mst(4, edges)
print(f"MST total weight: {weight}")  # Output: 6 (edges: 1-2 (1), 1-3 (2), 0-2 (3))
print(f"MST edges: {mst}")

Prim's Algorithm:

import heapq

def prim_mst(n, edges):
    """
    Builds MST using Prim's algorithm starting from node 0.
    edges: list of (u, v, weight) for undirected graph.
    """
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    visited = [False] * n
    heap = [(0, 0, -1)]  # (weight, node, parent)
    total_weight = 0
    mst_edges = []
    nodes_in_mst = 0
    
    while heap and nodes_in_mst < n:
        weight, node, parent = heapq.heappop(heap)
        if visited[node]:
            continue
        visited[node] = True
        nodes_in_mst += 1
        if parent != -1:
            mst_edges.append((parent, node, weight))
            total_weight += weight
        for neighbor, w in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(heap, (w, neighbor, node))
    
    return total_weight, mst_edges

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
weight, mst = prim_mst(4, edges)
print(f"MST total weight: {weight}")  # Output: 6

Common Interview Graph Problem Patterns

Pattern 1: Grid as Implicit Graph

Many problems use a 2D grid where each cell is a node, and edges connect adjacent cells. Classic examples: Number of Islands, Flood Fill, Walls and Gates, Shortest Path in a Grid with obstacles. The graph is implicit — you don't explicitly build an adjacency list; instead, you generate neighbors on the fly using direction arrays.

# Number of Islands (LeetCode 200)
def num_islands(grid):
    """
    Given a 2D grid of '1's (land) and '0's (water),
    count the number of islands.
    """
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited by sinking the land
        # Explore all four directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    
    return count

# Example
island_grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
print(num_islands(island_grid))  # Output: 3

Pattern 2: BFS for Shortest Path in Grid

When a grid problem asks for the shortest path or minimum steps with uniform costs, BFS is the natural choice because it guarantees the first time you reach the target is via the shortest path.

from collections import deque

def shortest_path_in_grid(grid, start, end):
    """
    Grid with 0 = open cell, 1 = obstacle.
    Returns minimum steps from start to end, or -1 if unreachable.
    """
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    er, ec = end
    
    if grid[sr][sc] == 1 or grid[er][ec] == 1:
        return -1
    
    queue = deque([(sr, sc, 0)])  # (row, col, steps)
    visited = set()
    visited.add((sr, sc))
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == (er, ec):
            return steps
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, steps + 1))
    
    return -1

# Example
maze = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [1, 0, 1, 0]
]
print(shortest_path_in_grid(maze, (0, 0), (3, 3)))  # Output: 6

Pattern 3: Graph Coloring / Bipartite Check

Determining if a graph is bipartite (can be colored with 2 colors such that no adjacent nodes share the same color) is a common interview problem. It's solved with BFS or DFS by attempting to color the graph and checking for conflicts.

def is_bipartite(n, edges):
    """
    Returns True if the undirected graph is bipartite.
    """
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    colors = [0] * n  # 0 = uncolored, 1 = red, -1 = blue
    
    def bfs_check(start):
        queue = deque([start])
        colors[start] = 1
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == 0:
                    colors[neighbor] = -colors[node]
                    queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False  # same color on both ends = not bipartite
        return True
    
    for i in range(n):
        if colors[i] == 0:
            if not bfs_check(i):
                return False
    return True

# Example: a graph that is bipartite (no odd-length cycles)
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]  # 4-cycle, even length
print(is_bipartite(4, edges))  # Output: True

# Example: triangle graph (odd cycle, not bipartite)
edges_triangle = [(0, 1), (1, 2), (2, 0)]
print(is_bipartite(3, edges_triangle))  # Output: False

Pattern 4: Word Ladder / State Space Graph

Problems like Word Ladder (LeetCode 127) model the search space as a graph where nodes are words and edges connect words differing by one character. Building the graph explicitly can be expensive, so generating neighbors on the fly is more efficient.

from collections import deque

def word_ladder_length(begin_word, end_word, word_list):
    """
    Returns the number of words in the shortest transformation sequence
    from beginWord to endWord, changing one letter at a time.
    """
    word_set = set(word_list)
    if end_word not in word_set:
        return 0
    
    queue = deque([(begin_word, 1)])  # (word, steps including beginWord)
    visited = {begin_word}
    
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        
        # Generate all possible one-letter transformations
        for i in range(len(word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if char == word[i]:
                    continue
                next_word = word[:i] + char + word[i+1:]
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))
    
    return 0

# Example
word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
print(word_ladder_length("hit", "cog", word_list))  # Output: 5
# Path: hit -> hot -> dot -> dog -> cog (or hot -> lot -> log -> cog)

Pattern 5: Clone Graph

Cloning a graph (LeetCode 133) tests your ability to traverse a graph while building a deep copy. It requires a mapping from original nodes to cloned nodes to handle cycles correctly.

class GraphNode:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    """
    Given a reference to a node in a connected undirected graph,
    return a deep copy of the graph.
    """
    if not node:
        return None
    
    # Map original nodes to cloned nodes
    cloned = {}
    
    def dfs(original):
        if original in cloned:
            return cloned[original]
        # Create clone
        copy = GraphNode(original.val)
        cloned[original] = copy
        # Recursively clone neighbors
        for neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy
    
    return dfs(node)

# Example usage:
# node1 = GraphNode(1)
# node2 = GraphNode(2)
# node3 = GraphNode(3)
# node1.neighbors = [node2, node3]
# node2.neighbors = [node1, node3]
# node3.neighbors = [node1, node2]
# cloned_graph = clone_graph(node1)
# print(cloned_graph.val)  # Output: 1
# print(len(cloned_graph.neighbors))  # Output: 2

Pattern 6: Graph with Weighted Edges and Limited Stops

Some problems modify standard algorithms by adding constraints like "at most K stops" (LeetCode 787: Cheapest Flights Within K Stops). This requires a variation of Bellman-Ford or a BFS that tracks stops.

import heapq

def cheapest_flight_within_k_stops(n, flights, src, dst, k):
    """
    flights: list of [from, to, price]
    Returns cheapest price from src to dst with at most k stops.
    """
    graph = [[] for _ in range(n)]
    for u, v, price in flights:
        graph[u].append((v, price))
    
    # (cost, node, stops_used)
    heap = [(0, src, 0)]
    # Track best cost for each (node, stops) state
    best = [[float('inf')] * (k + 2) for _ in range(n)]
    best[src][0] = 0
    
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops > k or cost > best[node][stops]:
            continue
        for neighbor, price in graph[node]:
            new_cost = cost + price
            new_stops = stops + 1
            if new_stops <= k + 1 and new_cost < best[neighbor][new_stops]:
                best[neighbor][new_stops] = new_cost
                heapq.heappush(heap, (new_cost, neighbor, new_stops))
    
    return -1

# Example
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
print(cheapest_flight_within_k_stops(3, flights, 0, 2, 1))  # Output: 200 (0->1->2)

Best Practices for Graph Interview Problems

• Clarify the graph type upfront. Ask: "Is the graph directed or undirected? Are there cycles? Are edge weights non-negative? Is it connected?" These answers dictate your algorithm choice.
• Choose the right representation. Default to adjacency lists. Only use adjacency matrices if the graph is dense (E ≈ V²) or you need constant-time edge weight lookups.
• Draw the graph on the whiteboard. Visualizing nodes and edges helps you spot patterns, test your algorithm manually, and communicate your thought process to the interviewer.
• Handle disconnected graphs. Many candidates forget that a graph might have multiple components. Always consider whether you need to iterate over all nodes to find unvisited ones.
• Use BFS for shortest path in unweighted graphs. This is a rule of thumb that interviewers expect you to know immediately. BFS guarantees optimality when all edges have the same cost.
• Use Dijkstra for weighted graphs with non-negative weights. Explain why Dijkstra works (greedy, expanding smallest tentative distance) and mention the heap optimization gives O((V+E) log V).
• Mention Union-Find for connectivity and cycle detection. When a problem involves dynamic connectivity or checking if two nodes are in the same component after a series of edge additions, Union-Find with path compression and union by rank gives near O(1) operations.
• Track visited nodes carefully. In BFS/DFS, mark nodes as visited when you add them to the queue/stack (or when you start processing), not when you pop them. This prevents duplicate additions and infinite loops.
• Discuss time and space complexity naturally. For BFS/DFS on adjacency lists: O(V + E) time, O(V) space. For Dijkstra: O((V + E) log V). For Union-Find: O(α(n)) amortized. State these confidently.
• Test your algorithm on a small example. Walk through your code with a simple graph (3-4 nodes) to catch bugs before claiming you're done. Interviewers value this verification step.
• Consider edge cases. Empty graph, single node, disconnected components, negative weights (use Bellman-Ford), self-loops, duplicate edges. Mentioning these shows thoroughness.
• When stuck, try converting the problem to a graph. Many problems that don't look graph-like (e.g., "minimum number of keypresses," "word transformation sequences") are actually implicit graph problems where states are nodes and transitions are edges.

Putting It All Together: A Mock Interview Walkthrough

Let's simulate how you'd approach a graph problem in an actual interview. Consider this prompt:

"You have a network of n computers labeled 0 to n-1. You are given an initial computer infected with a virus, and a list of connections between computers. The virus spreads to directly connected computers every second. Return how many seconds it takes for all computers to be infected. If not all computers can be infected, return -1."

Step 1: Clarify. "Is the graph undirected? Yes. Are there any disconnected components? Possibly. Is the initial infected computer given as a single integer? Yes."

Step 2: Recognize the pattern. This is a BFS problem — we need the time (level) when the last node is visited, which is the maximum distance from the source in an unweighted graph.

Step 3: Propose the algorithm. BFS from the initial infected node, tracking the maximum distance. After BFS, check if all nodes were visited; if not, return -1.

Step 4: Write the code.

from collections import deque

def virus_infection_time(n, edges, initial):
    # Build undirected adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    queue = deque([(initial, 0)])  # (node, time_in_seconds)
    visited = [False] * n
    visited[initial] = True
    max_time = 0
    infected_count = 1
    
    while queue:
        node, time = queue.popleft()
        max_time = max(max_time, time)
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                infected_count += 1
                queue.append((neighbor, time + 1))
    
    if infected_count < n:
        return -1  # not all computers reachable
    return max_time

# Example
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
print(virus_infection_time(5, edges, 2))  # Output: 2 (2->1, 2->3 in 1 sec, then 1->0, 3->4 in 2 sec)

# Disconnected example
edges_disconnected = [(0, 1), (2, 3)]
print(virus_infection_time(4, edges_disconnected, 0))  # Output: -1

Step 5: Analyze complexity. "Building the graph takes O(V + E). BFS takes O(V + E) time and O(V) space for the queue and visited array. Total time O(V + E), space O(V)."