Graphs and Graph Algorithms Questions

Direct answer

A graph is bipartite when its nodes split into two groups such that every edge connects a node in one group to a node in the other, never two nodes within the same group. The standard test is a two-coloring traversal: pick an unvisited node, color it, breadth-first search (BFS) or depth-first search (DFS) outward assigning every newly discovered neighbor the opposite color of whoever discovered it, and declare the graph non-bipartite the moment an edge is found connecting two nodes already colored the same. This runs in $O(V+E)$ time and, since real input is rarely one connected blob, must restart the coloring process from every not-yet-visited node to correctly cover disconnected components.

Structured elaboration

Algorithmic steps.

1. Maintain a color map (or array), initially empty/unset for every node.
2. For every node in the graph not yet colored: assign it color 0, then traverse outward (BFS or DFS) coloring each newly reached neighbor the opposite color of the node that reached it.
3. During the traversal, if an edge is found connecting two nodes that are ALREADY colored and share the same color, the graph is not bipartite; report this immediately, no need to finish coloring.
4. If every component colors without conflict, the graph is bipartite, and the accumulated coloring is a valid two-group partition.

Complexity. $O(V+E)$: identical to a plain traversal, since coloring adds only constant work per node and per edge on top of standard BFS/DFS.

Handling disconnected graphs. Each connected component is bipartite or not fully independently of every other component (there is no edge between components to create a cross-component constraint), so step 2's outer loop over every node, not just a single arbitrary start, is what makes the check correct on realistic, likely-disconnected input rather than only on a single connected blob.

A constraint-checking use case: consistency checking in a labeling or pairing problem. Bipartiteness testing is a natural fit whenever a system needs to verify a set of pairwise "must differ" or "must be mutually exclusive" constraints is jointly satisfiable with only two labels. Concretely: given a set of items and a collection of pairwise "these two must NOT receive the same label" constraints (for example, entities that a weak-supervision or crowd-labeling pipeline has flagged as definitely-conflicting, or tasks that must run in different phases because they compete for the same exclusive resource), model each item as a node and each "must differ" constraint as an edge. The constraint set is satisfiable with exactly two labels if and only if this constraint graph is bipartite; the two-coloring, if one exists, IS a valid assignment, and the specific conflicting edge found on failure (when the algorithm returns non-bipartite) pinpoints exactly which pair of constraints is jointly unsatisfiable, useful for surfacing to a human reviewer rather than just reporting "no valid assignment exists" with no further detail.

Trade-offs and pitfalls

• Common mistake: only checking connectivity from a single starting node. On a disconnected constraint graph, this silently leaves later components unchecked, which could wrongly report a labeling problem as satisfiable when a conflict actually exists in an unreached component.
• Bipartiteness answers exactly "can this be done with TWO labels," not "how many labels are actually needed." If the true minimum number of labels needed to satisfy every pairwise "must differ" constraint is 3 or more (a general graph-coloring problem, which is NP-hard in general, unlike the polynomial-time bipartite case), a bipartiteness check will correctly report the graph as non-bipartite, but that result alone does not tell you the actual minimum label count, only that two is not enough.
• The distinction between "must differ" pairwise constraints (which map naturally to bipartiteness) and general compatibility scoring (which does not) matters: bipartiteness testing is the right tool specifically for hard binary exclusion constraints, not for a softer "these two are UNLIKELY to belong together" signal, which calls for a different technique (for example, a weighted graph-partitioning or clustering approach) rather than an exact feasibility check.
• An odd-length cycle among the constraints is exactly what makes two labels insufficient: three items that must all pairwise differ from each other cannot be satisfied with only two labels (by the pigeonhole principle, two of the three would have to share a label), and this is precisely the 3-cycle case the two-coloring algorithm detects as its simplest failing example.

Direct answer

Running depth-first search (DFS) on a directed graph and recording, for every vertex $v$, a discovery time $d[v]$ (when DFS first reaches $v$) and a finish time $f[v]$ (when DFS has fully explored everything reachable from $v$ and returns), every edge $(u,v)$ falls into exactly one of four categories based on how those two intervals relate: tree, forward, back, or cross.

Structured elaboration

• Tree edge. $(u,v)$ is the edge DFS actually used to first discover $v$; $v$ becomes a child of $u$ in the DFS tree. Formally, $d[u] < d[v] < f[v] < f[u]$, and $v$'s discovery immediately follows $u$'s.
• Forward edge. $(u,v)$ points to a vertex $v$ that is a descendant of $u$ in the DFS tree, but was NOT the edge that first discovered $v$ (some other tree edge got there first, deeper in the recursion). Formally, the same interval containment as a tree edge, $d[u] < d[v] < f[v] < f[u]$, but $(u,v)$ is not the tree edge itself.
• Back edge. $(u,v)$ points to an ANCESTOR of $u$ in the DFS tree, that is, to a vertex still "in progress" (discovered but not yet finished) when $u$ is processed. Formally, $d[v] < d[u] < f[u] < f[v]$, the ancestor's interval contains the descendant's.
• Cross edge. $(u,v)$ points to a vertex $v$ that is neither an ancestor nor a descendant of $u$, typically in an already-finished, unrelated branch of the DFS tree. Formally, the two intervals are disjoint: $f[v] < d[u]$.

Relation to cycle detection. A directed graph contains a cycle if and only if DFS finds at least one back edge. This is because a back edge $(u,v)$ points at a vertex $v$ still on the current recursion path (an ancestor), so the tree-path from $v$ down to $u$, plus the edge $u \to v$, forms an explicit cycle. No back edge means no such "return to an in-progress ancestor" ever happens, which is exactly the absence of a directed cycle.

Relation to topological sorting. A directed acyclic graph (DAG, a directed graph with no cycles) has no back edges by the fact above. For every edge $(u,v)$ in a DAG, DFS's structure guarantees $f[u] > f[v]$ (this holds for tree, forward, and cross edges alike, and back edges cannot occur). So sorting vertices by DECREASING finish time produces an order where every edge points from an earlier vertex to a later one, exactly the definition of a valid topological order.

Worked example

Take the directed graph: $A \to B$, $A \to C$, $B \to C$, $C \to D$, $D \to B$. Running DFS from A, visiting neighbors in listed order:

Classification summary: $A\to B$ and $B\to C$ (the first time, via $A \to B \to C$) and $C \to D$ are TREE edges (they are the edges DFS actually used to first discover B, C, and D). $D \to B$ is a BACK edge (reveals the cycle $B \to C \to D \to B$). $A \to C$ is a FORWARD edge (C already reachable and discovered as A's descendant before this edge is examined). This graph has no cross edge at all; a genuine cross-edge example needs two sibling subtrees, for instance adding a vertex E with edges $A \to E$ and $E \to C$ after C is already finished would make $E \to C$ a cross edge (pointing into an already-finished, unrelated branch).

Trade-offs and pitfalls

• Common mistake: trying to classify an edge using only discovery time, without finish time. Discovery time alone cannot distinguish a forward edge from a cross edge in some graph shapes; the finish-time containment (or lack of it) is what actually distinguishes ancestor/descendant relationships from unrelated branches.
• Undirected graphs only have tree edges and back edges, no forward or cross edges. This is because in an undirected graph, an edge $(u,v)$ examined from $u$ toward an already-visited $v$ is the exact same edge as $(v,u)$ examined earlier from $v$'s own exploration, so what would be a "forward" edge from one direction is simply the same back edge already counted from the other direction; the four-way classification is specifically a directed-graph concept.
• The back-edge-implies-cycle result is exactly what a production cycle detector (for example, checking a dependency graph for circular dependencies) implements under the hood, usually via the lighter "white/gray/black" color-marking scheme rather than literal discovery/finish timestamps, gray is equivalent to "discovered but not yet finished," so a back edge is precisely an edge into a currently-gray node.

Direct answer

Maintaining connected components under insertions alone is a solved, cheap problem: Union-Find handles it in amortized $O(\alpha(n))$ per insertion. Deletions are the genuinely hard part, because Union-Find's tree-merging structure has no efficient inverse: once two sets are merged, there is no cheap way to ask "if I remove this one edge, does the merged set need to split back into two." The practical engineering answer is almost never "support arbitrary deletions with full generality," it is to constrain the problem: batch deletions and periodically rebuild, or accept an offline model where the full sequence of operations is known in advance, or reach for a genuinely dynamic data structure (Euler tour trees, link-cut trees) only when the deletion rate and latency requirements truly demand it.

Structured elaboration

Why insertions are easy. Each new edge is one union call. Amortized cost per operation is $O(\alpha(n))$, and the structure never needs to "undo" anything to support more insertions, so an insert-heavy or insert-only workload is a non-issue for Union-Find.

Why deletions are hard. When an edge is removed, the two nodes it connected might still be connected through some OTHER path (so nothing changes), or that edge might have been the only path between two halves of what is now two separate components (so the structure must split). Union-Find's tree shape after path compression has discarded the information needed to tell these two cases apart cheaply: it only remembers "these nodes ended up under the same root at some point," not "here is the specific set of edges that currently justifies that." Determining which case applies in general requires re-deriving connectivity from the remaining edges, which is exactly the expensive operation Union-Find was built to avoid.

Three practical strategies, in order of increasing sophistication:

1. Full rebuild on every batch of deletions. Accumulate deletions for some time window or count threshold, then rebuild the entire Union-Find structure from the current live edge set. Cost: $O(E)$ per rebuild, amortized over however many deletions triggered it. This is the simplest strategy and is often sufficient when connectivity queries can tolerate being slightly stale (answered against the last completed rebuild) rather than reflecting every deletion instantly.
2. Offline divide-and-conquer with rollback, when the full sequence of insertions, deletions, and queries is known ahead of time (a genuinely offline setting, common in batch analytics jobs). Each edge's active time interval is computed in advance, and a Union-Find variant that supports undoing unions (by NOT using path compression, only union by size, and keeping an explicit undo stack) processes the timeline via a segment tree over time, applying and rolling back unions as it recurses. This achieves $O((V + E + Q) \log T)$ total for $T$ time steps and $Q$ queries, at the cost of needing the full operation sequence upfront, which rules it out for a genuinely live, open-ended stream.
3. Fully dynamic connectivity structures (Euler tour trees, or the Holm-de Lichtenberg-Thorup structure), which support both insertion and deletion in $O(\log^2 n)$ amortized time without needing the future operation sequence in advance. These exist and are the theoretically correct answer to "support both directions online," but they carry real implementation complexity (multiple levels of spanning-forest bookkeeping) well beyond what most production systems justify building or maintaining in-house.

Amortized complexity summary:

Worked example

For a near-real-time dashboard showing which servers are currently mutually reachable (an operational monitoring use case), a reasonable strategy is strategy 1, tuned: rebuild the Union-Find structure on a fixed cadence (say, once per minute, driven by the dashboard's own refresh interval, not by a fixed edge count) from the live edge set as of that moment, and serve all connectivity queries against the most recent rebuild in between. If a specific incident-response workflow needs connectivity reflecting deletions within seconds rather than up to a minute of staleness, that workflow can additionally maintain its OWN small Union-Find rebuilt just over the specific subgraph relevant to the incident, rather than paying the cost of low-latency full dynamic connectivity across the entire graph. The batching threshold (time-based vs count-based) is a product/operational decision, not a purely algorithmic one: a time-based cadence gives predictable staleness bounds, while a count-based cadence (rebuild after every $B$ deletions) gives a predictable amortized cost per deletion but an unpredictable staleness bound if deletions arrive in bursts.

Trade-offs and pitfalls

• Common mistake: reaching for a fully dynamic connectivity structure by default. These are real, correct, and asymptotically strong, but the implementation complexity is high enough that most production systems are better served by batching plus a staleness bound the business can actually tolerate; reserve the fully dynamic structure for cases where sub-second correctness after every single deletion is a hard requirement, not a nice-to-have.
• Common mistake: conflating "offline" (full operation sequence known in advance) with "batched" (deletions grouped into windows, but the future is still unknown). The divide-and-conquer-with-rollback technique needs the FULL timeline upfront; it cannot be run incrementally against a live, open-ended stream, which makes it a poor fit for a live dashboard and a good fit for a nightly batch-analytics reprocessing job over a day's worth of logged topology changes.
• A rebuild-based strategy's staleness bound is a first-class design parameter, not an afterthought: it must be stated and monitored (rebuild latency drifting up as the graph grows is a real operational risk), not left as an implicit assumption that "the rebuild is fast enough."
• Query semantics need to be explicit about what "connected" means during a batching window: does a query answered mid-batch reflect the edges as of the LAST completed rebuild, or does it block until the next rebuild finishes? Silently mixing the two within one system produces confusing, non-reproducible answers to the same query asked moments apart.

Direct answer

Enumerate simple paths (no repeated vertex) up to $k$ edges using depth-first search (DFS) with backtracking: extend the current path by one unvisited neighbor at a time, record a match whenever the destination is reached, and undo the last step (backtrack) once a branch is exhausted or the length budget is used up. In production, this must ship with explicit safeguards, a cap on the number of returned paths and, ideally, a generator interface, since the number of simple paths can grow exponentially with $k$.

Structured elaboration

Why backtracking, not plain DFS. A plain DFS that only tracks a global visited set would incorrectly mark a node as permanently visited the first time any path reaches it, preventing that node from appearing in a DIFFERENT simple path later. Path enumeration needs "visited along the CURRENT path only," which is exactly what backtracking provides: add the node to the path (and a per-path visited set) on the way down, remove it again on the way back up, so the same node can legitimately appear in multiple distinct paths explored one after another.

Why the length cap matters structurally, not just as an optimization. Once the current path already has $k$ edges, no further extension can still be a valid answer, so the recursion should stop extending at that point regardless of whether the destination was reached, this prunes the search rather than merely limiting the OUTPUT after the fact.

Production safeguards. Two independent knobs matter: a max_paths cap on how many results are returned (protects the CALLER from an unbounded result set) and, in a fuller production version, a wall-clock or work-based timeout (protects the WORKER from spending unbounded time on a single request); yielding results incrementally via a generator lets a caller consume the first several paths without waiting for, or paying the memory cost of, an exhaustive enumeration.

Worked example

from typing import Dict, Iterable, List

def enumerate_simple_paths(adj: Dict[int, Iterable[int]], src: int, dst: int, k: int,
                            max_paths: int = None) -> List[List[int]]:
    '''DFS/backtracking enumeration of simple (no repeated node) paths from src to dst
    using at most k edges. max_paths caps output size for production safety.'''
    results: List[List[int]] = []

    def backtrack(node, path, path_set):
        if max_paths is not None and len(results) >= max_paths:
            return
        if node == dst:
            results.append(list(path))
            return
        if len(path) - 1 >= k:
            return
        for nbr in adj.get(node, ()):
            if nbr in path_set:
                continue
            path.append(nbr)
            path_set.add(nbr)
            backtrack(nbr, path, path_set)
            path.pop()
            path_set.discard(nbr)

    backtrack(src, [src], {src})
    return results

if __name__ == "__main__":
    # Diamond graph (two disjoint routes from 0 to 5) with an extra edge 4->0
    # that would create a cycle if the visited-per-path guard were missing.
    adj = {
        0: [1, 2],
        1: [3],
        2: [3],
        3: [4],
        4: [0, 5],
        5: [],
    }
    all_paths = enumerate_simple_paths(adj, 0, 5, k=10)
    print("All simple paths 0 -> 5 (k<=10):", all_paths)
    print("count:", len(all_paths))

    capped = enumerate_simple_paths(adj, 0, 5, k=3)
    print("Paths 0 -> 5 with at most 3 edges:", capped, "(expect none: shortest path needs 4 edges)")

    exactly4 = enumerate_simple_paths(adj, 0, 5, k=4)
    print("Paths 0 -> 5 with at most 4 edges:", exactly4)

    # max_paths safeguard against combinatorial blow-up
    fanout = {0: list(range(1, 21))}
    for i in range(1, 21):
        fanout[i] = [100]
    fanout[100] = []
    capped_count = enumerate_simple_paths(fanout, 0, 100, k=2, max_paths=5)
    print("Wide fan-out graph has 20 possible 2-edge paths; max_paths=5 caps output at:", len(capped_count))

Output (actually executed with python3):

All simple paths 0 -> 5 (k<=10): [[0, 1, 3, 4, 5], [0, 2, 3, 4, 5]]
count: 2
Paths 0 -> 5 with at most 3 edges: [] (expect none: shortest path needs 4 edges)
Paths 0 -> 5 with at most 4 edges: [[0, 1, 3, 4, 5], [0, 2, 3, 4, 5]]
Wide fan-out graph has 20 possible 2-edge paths; max_paths=5 caps output at: 5

Complexity

• Worst case time and space: $O(b^k)$ where $b$ is the branching factor, exponential in $k$, since the number of simple paths itself can be exponential in a densely connected graph.
• Memory for the active recursion: $O(k)$ per path in progress (the current path and its per-path visited set), independent of how many completed paths have been found so far, if results are streamed rather than accumulated.
• With max_paths set, the function still explores in the worst case some unbounded-looking branches before finding enough valid paths, worst-case time is not improved by the cap alone in an adversarial graph, only the OUTPUT size is bounded; a true worst-case time bound needs a separate node/step budget, not shown here.

Edge cases

• src == dst: the first check (node == dst) fires immediately, returning [[src]], a trivial zero-edge path.
• No path within $k$ edges: returns an empty list, demonstrated above with the k=3 case.
• Cycles in the input graph (the 4->0 edge above): handled safely, since path_set prevents revisiting any node already on the CURRENT path, so the cycle simply cannot be taken without repeating a node, which the simple-path definition already forbids.
• Very wide fan-out: demonstrated with the 20-branch example, max_paths caps the returned count without needing the caller to consume an unbounded generator.

Trade-offs and pitfalls

• Common mistake: using a single, path-independent visited set shared across the whole search instead of a per-path one; this would incorrectly prevent a node from ever being reused in a different candidate path, undercounting or completely missing valid simple paths that happen to share an intermediate node.
• For weighted graphs, replace the edge-count budget k with a cost budget, and prune whenever the accumulated path cost exceeds it, rather than counting edges; this changes the pruning condition but not the backtracking structure.
• Approximate path-counting (for example a random-walk-based Monte Carlo estimate, or dynamic-programming counts of paths WITHOUT materializing them, only valid when repeated vertices are allowed or the graph is a DAG so simple-path counting is tractable) is worth reaching for once exact enumeration itself, not just returning the results, becomes the bottleneck, for instance when the caller only needs "roughly how many paths exist," not the paths themselves.
• Parallelizing across workers: the search tree can be split at the first branching level (each worker owns one of src's neighbors as its subtree root) with max_paths tracked as either a shared, coordinated budget or an independent per-worker budget depending on whether a hard global cap or a best-effort cap is required.

Direct answer

A grid of land ('1') and water ('0') cells is an implicit graph where each land cell is a node connected to its up-to-four orthogonal land neighbors; counting islands is counting connected components. Scan every cell in row-major order, and each time an unvisited '1' is found, that is a brand-new island: run depth-first search (DFS) or breadth-first search (BFS) from it to mark every reachable land cell as visited, so the outer scan never counts the same island twice.

Structured elaboration

In-place marking versus a visited set. Flipping a visited land cell from '1' to '0' directly in the grid is the simplest way to mark it: no extra memory beyond the traversal's own stack or queue, but it destroys the caller's input, which is unacceptable if the grid needs to be reused or read again afterward. A separate visited boolean matrix (or a set of coordinates) avoids mutating the input at the cost of $O(R \times C)$ extra memory. The choice is a straightforward trade: mutate for memory efficiency when the caller has explicitly handed over ownership of the grid, use a visited structure otherwise.

Handling non-rectangular (jagged) input. A grid is not guaranteed to have every row the same length; bounds-checking a candidate neighbor must check against THAT row's own length (c < len(grid[r])), not a single global column count, or a jagged grid can silently index out of bounds on a shorter row.

Worked example

from typing import List

def num_islands(grid: List[List[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows = len(grid)

    def in_bounds(r, c):
        return 0 <= r < rows and 0 <= c < len(grid[r])

    islands = 0
    for r in range(rows):
        for c in range(len(grid[r])):
            if grid[r][c] == '1':
                islands += 1
                stack = [(r, c)]
                grid[r][c] = '0'  # mark on discovery, in place
                while stack:
                    x, y = stack.pop()
                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nx, ny = x + dx, y + dy
                        if in_bounds(nx, ny) and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            stack.append((nx, ny))
    return islands

if __name__ == "__main__":
    grid1 = [
        list("11000"),
        list("11000"),
        list("00100"),
        list("00011"),
    ]
    print("grid1 islands:", num_islands([row[:] for row in grid1]))

    print("empty grid:", num_islands([]))

    jagged = [list("10"), list("111"), list("0")]
    print("jagged grid islands:", num_islands([row[:] for row in jagged]))

    all_water = [list("000"), list("000")]
    print("all water:", num_islands([row[:] for row in all_water]))

    def num_islands_bfs_reference(grid):
        from collections import deque
        if not grid or not grid[0]:
            return 0
        rows = len(grid)
        visited = [[False] * len(row) for row in grid]
        count = 0
        for r in range(rows):
            for c in range(len(grid[r])):
                if grid[r][c] == '1' and not visited[r][c]:
                    count += 1
                    q = deque([(r, c)])
                    visited[r][c] = True
                    while q:
                        x, y = q.popleft()
                        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < rows and 0 <= ny < len(grid[nx]) and grid[nx][ny] == '1' and not visited[nx][ny]:
                                visited[nx][ny] = True
                                q.append((nx, ny))
        return count

    ref = num_islands_bfs_reference([row[:] for row in grid1])
    print("Matches independent, non-mutating BFS reference:", ref == num_islands([row[:] for row in grid1]))

Output (actually executed with python3):

grid1 islands: 3
empty grid: 0
jagged grid islands: 1
all water: 0
Matches independent, non-mutating BFS reference: True

grid1 has three islands by hand-count: the 2x2 block in the top-left, the single cell at (2,2), and the two-cell block at (3,3)-(3,4). The jagged grid ["10","111","0"] has one island, since (0,0) connects vertically to (1,0), which connects horizontally to (1,1) and (1,2), all four cells joined into one component despite the rows having different lengths.

Complexity

Time $O(R \times C)$: the outer double loop visits every cell once, and the inner DFS/BFS, across the entire run, visits every land cell exactly once (each is marked immediately on discovery, never re-pushed). Space $O(R \times C)$ worst case for the traversal stack (a grid that is entirely one giant island) in the in-place version, or $O(R \times C)$ for the visited matrix plus the stack in the non-mutating version.

Edge cases

• Empty grid, or a grid whose first row is empty: not grid or not grid[0] catches both and returns 0.
• Non-rectangular (jagged) rows: handled by checking each candidate neighbor's bound against that specific row's own length, not a shared column count, as shown above.
• All water: the outer loop never finds a '1', returns 0 without ever starting a traversal.
• A single-cell island, or the entire grid being one connected island: both fall out naturally from the same code path with no special-casing.
• Diagonal adjacency: not counted by this implementation (only the four orthogonal directions), matching the standard problem definition; if diagonal adjacency were required, adding the four diagonal offsets to the direction list is the only change needed, and doing so can only merge islands, never split them, so the count can only decrease or stay the same relative to orthogonal-only adjacency.

Trade-offs and pitfalls

• Recursion depth at scale. A naive recursive DFS on a very large, single-island grid (for example 10,000 x 10,000, all land) recurses as deep as the island's longest simple path, which can exceed a language's default recursion limit; the iterative, explicit-stack version above sidesteps this entirely, which is why it is written iteratively rather than as a simpler-looking recursive function.
• Common mistake: checking visited (or flipping to '0') only when a cell is POPPED from the stack rather than when it is first discovered and PUSHED. This lets the same cell be pushed multiple times by different neighbors before any of those pushes gets processed, wasting work and, in pathological cases, inflating the stack far beyond the actual number of distinct cells.
• Common mistake: using a single shared column-count bound check on a grid that is not actually rectangular, which either throws an index error on a shorter row or, worse, silently reads stale data from a previous row's memory layout depending on the language and data structure.
• Diagonal-connectivity as a difficulty-bump variant. Making 4-direction versus 8-direction connectivity a runtime parameter (rather than hardcoded) is a natural follow-up: the algorithm's shape does not change, only the directions list does, but it is worth naming explicitly since some interviewers use it specifically to see whether a candidate treats "island" as a fixed rule or a configurable one.