Graphs and Graph Algorithms Questions

Direct answer

Compute each task's earliest start and earliest finish time with a single forward pass over a topological ordering of the dependency DAG: a task's earliest start is the maximum earliest-finish among all its direct predecessors (0 if it has none), and its earliest finish is its earliest start plus its own duration. The overall project completion time is the maximum earliest-finish across every task, and the critical path (the sequence of tasks that directly determines that completion time, with zero slack) is the longest path through the DAG when edges are weighted by task duration; this is exactly the classical critical path method (CPM), computed as a longest-path-in-a-DAG problem using topological order in place of Dijkstra/Bellman-Ford (neither of which is needed, since a DAG's topological order alone is sufficient to relax every edge exactly once in a correct dependency order).

Structured elaboration

Why topological order is sufficient (no shortest/longest-path algorithm needed). A task's earliest finish only depends on its predecessors' earliest finish times, which must already be known before that task can be processed. A topological order guarantees every predecessor of a task appears before it in the processing sequence, so a single forward pass, processing tasks in topological order and updating each successor's earliest-start as soon as a predecessor finishes, correctly computes every earliest-finish time in one $O(V+E)$ pass, with no need for a priority queue or repeated relaxation the way Dijkstra or Bellman-Ford would require.

Algorithm (Kahn's-algorithm-style, computing earliest-finish as tasks are dequeued):

1. Compute in-degree for every task; task with in-degree 0 have earliest_start = 0.
2. Process tasks via a queue seeded with all in-degree-0 tasks (standard Kahn's algorithm). When a task u is dequeued: earliest_finish[u] = earliest_start[u] + duration[u]. For every successor v of u: earliest_start[v] = max(earliest_start[v], earliest_finish[u]), decrement v's in-degree, and enqueue v once its in-degree reaches 0.
3. The project completion time is max(earliest_finish.values()) across all tasks.

Modifying for resource-constrained scheduling (limited parallel workers). The unconstrained calculation above implicitly assumes UNLIMITED parallelism, every task with satisfied dependencies can start immediately. With only k workers, tasks whose dependencies are satisfied but who cannot get a free worker must WAIT even though the dependency graph alone would allow them to start, which turns this from a pure graph problem into resource-constrained project scheduling (RCPSP), a materially harder problem: RCPSP is NP-hard in general, unlike the polynomial-time unconstrained CPM calculation. A common practical approach is a priority-based simulation: at every point in simulated time, among all tasks whose dependencies are satisfied and are not yet running, greedily assign available workers by some priority rule (commonly least-slack-first, prioritizing tasks on or nearest to the critical path, since delaying THOSE tasks directly delays the project, while tasks with slack can absorb some worker-availability delay without affecting the overall completion time).

Worked example

from collections import deque
from typing import Dict, List

def earliest_completion(n: int, adj: Dict[int, List[int]], duration: Dict[int, int]):
    indeg = {u: 0 for u in range(n)}
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    q = deque([u for u in range(n) if indeg[u] == 0])
    topo = []
    earliest_start = {u: 0 for u in range(n)}
    earliest_finish = {}
    while q:
        u = q.popleft()
        topo.append(u)
        earliest_finish[u] = earliest_start[u] + duration[u]
        for v in adj.get(u, []):
            earliest_start[v] = max(earliest_start[v], earliest_finish[u])
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(topo) != n:
        raise ValueError("graph has a cycle; no valid topological order")
    return earliest_finish, max(earliest_finish.values()), topo

if __name__ == "__main__":
    # 6 tasks (0..5): 0=build(3h) -> 1=docs(1h), 2=test(2h)
    # 1=docs -> 3=review(2h); 2=test -> 3=review, 4=package(1h)
    # 3=review -> 5=release(1h); 4=package -> 5=release
    n = 6
    duration = {0: 3, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1}
    adj = {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5], 5: []}
    finish, total, topo = earliest_completion(n, adj, duration)
    print("topological order:", topo)
    print("earliest finish times:", finish)
    print("project completion time:", total)
    serial_total = sum(duration[u] for u in topo)
    print("fully-serial (1 worker) total:", serial_total)

Output:

topological order: [0, 1, 2, 3, 4, 5]
earliest finish times: {0: 3, 1: 4, 2: 5, 3: 7, 4: 6, 5: 8}
project completion time: 8
fully-serial (1 worker) total: 10

Hand trace confirms the algorithm: start(0)=0, finish(0)=3. start(1)=finish(0)=3, finish(1)=4. start(2)=finish(0)=3, finish(2)=5. start(3)=max(finish(1)=4, finish(2)=5)=5, finish(3)=7. start(4)=finish(2)=5, finish(4)=6. start(5)=max(finish(3)=7, finish(4)=6)=7, finish(5)=8. The critical path is 0-2-3-5 (durations 3+2+2+1=8), the longest chain of dependent tasks, exactly matching the computed project completion time of 8. With unlimited parallelism the project finishes in 8 hours; with only 1 worker (fully serial, everything runs one after another in ANY valid topological order), it takes the sum of all durations, 10 hours, a useful sanity bound: the true resource-constrained answer for any worker count between 1 and unlimited must fall between 8 (the critical path lower bound, unbeatable no matter how many workers) and 10 (the fully-serial upper bound) hours.

Trade-offs and pitfalls

• Common mistake: computing earliest-start/earliest-finish in an order that is topologically valid for the WRONG direction, or accidentally using arrival order instead of a true topological order; if any predecessor is processed after one of its successors, that successor's earliest-start would be computed using a stale (too-small) predecessor finish time, silently understating the true completion time.
• The unconstrained calculation ($k = \infty$ workers) is a LOWER BOUND, never the true answer once a worker limit is introduced; a design that reports the unconstrained critical-path length as "the" completion time when workers are actually limited is reporting an optimistic, achievable-only-under-infinite-parallelism number, not the real constrained schedule.
• RCPSP (resource-constrained scheduling) is NP-hard, so an exact optimal schedule for large task counts under a worker limit is not efficiently computable in general; production systems use heuristics (least-slack-first, critical-path-first) that are good in practice but not provably optimal, a trade-off worth naming explicitly rather than implying a limited-worker schedule can always be computed exactly and efficiently.
• The fully-serial bound (sum of all durations) is only a valid upper bound when there is exactly 1 worker; with k > 1 but k < infinity, the achievable completion time lies somewhere between the critical-path lower bound and the fully-serial upper bound, and where exactly depends on the specific priority heuristic used and the DAG's branching structure, not on a simple closed-form formula.

Direct answer

Prefer Union-Find when connectivity needs to be queried repeatedly against a growing (insert-only) graph, or when the graph arrives as a stream of edges that must never all be held in memory at once as an adjacency structure. Prefer DFS/BFS when you need the graph traversed only once (a single connected-components pass), when you need the actual member list or shape of each component (not just "are these two connected"), or when the graph already needs to be materialized in memory for other reasons anyway. Both give the same $O(V+E)$-class total cost for a one-shot components computation; the real difference is in incremental behavior and memory footprint, not raw speed for a single full pass.

Structured elaboration

Practical performance on large sparse graphs. For a single, one-time "compute all components now" pass, DFS/BFS and Union-Find are asymptotically equivalent: $O(V+E)$ for the traversal versus $O(E \cdot \alpha(n)) \approx O(E)$ for Union-Find (since $\alpha(n) \le 4$ in practice). On a sparse graph ($E = O(V)$, the common real-world case for social graphs, service topologies, and dependency graphs), both are effectively linear in $V$. The practical performance difference shows up in constant factors and access pattern: DFS/BFS needs random access into an adjacency structure (cache-friendly if built as compressed sparse row, less so as a hash-map-backed adjacency list), while Union-Find only ever touches two flat arrays indexed directly by node ID, which tends to have excellent cache locality regardless of how the edges happen to be ordered.

Memory.

Union-Find's memory advantage is specifically that it never needs random access back into the edge set once an edge has been processed; DFS/BFS inherently needs to revisit a node's neighbor list every time that node is reached, so the adjacency structure must stay resident for the traversal's duration.

Incremental update implications. This is the sharpest practical difference. Adding a new edge to an already-computed Union-Find result is cheap: one union call, $O(\alpha(n))$ amortized, no need to touch anything else. Adding a new edge after a DFS/BFS-computed component list, by contrast, requires either a fresh traversal from one of the edge's endpoints to merge two existing components (cheap if the components were tracked as explicit sets you can merge, expensive if you would naively recompute everything), or accepting that the previously-computed component list is now stale. Neither structure handles edge REMOVAL cheaply: DFS/BFS needs a full re-traversal of the affected component to determine if it split, and Union-Find has no "un-union" operation at all, so both degrade to "rebuild from scratch" (or a much more complex dedicated dynamic-connectivity structure) under deletions.

Worked example

Consider a service-dependency graph with 50,000 services (nodes) and 120,000 dependency edges (sparse, average out-degree 2.4), where the graph is rebuilt from a fresh edge list once per minute by a monitoring job, and additionally single new edges arrive in near-real-time as services register new dependencies between rebuilds.

• The once-per-minute full rebuild is a one-shot computation over the complete edge list either way: a DFS/BFS pass costs $O(V+E) = O(50{,}000 + 120{,}000) = O(170{,}000)$ node-and-edge touches; a Union-Find pass over the same 120,000 edges costs $O(E \cdot \alpha(n)) \approx O(120{,}000 \times 4) = O(480{,}000)$ amortized array operations, which is a larger constant-factor count of individual operations but each operation is a simple array read/write rather than a hash-map or adjacency-list lookup, so in practice the two approaches land in a similar wall-clock ballpark for this size; the choice would come down to which representation the rest of the monitoring job already needs (if it needs an adjacency structure for other purposes anyway, DFS/BFS reuses it for free).
• The near-real-time single-edge updates between rebuilds are where the two approaches diverge sharply: applying one new edge to an already-built Union-Find structure is a single $O(\alpha(n))$ union call, whereas correctly updating a DFS/BFS-derived component list for one new edge (without a full re-traversal) requires the monitoring job to have retained enough bookkeeping to merge two component records directly, which is realistically only clean to do if that bookkeeping itself amounts to reimplementing a Union-Find-like merge step on top of the traversal result.

Trade-offs and pitfalls

• Common mistake: treating this as purely an asymptotic-complexity question. For a single full pass, both are effectively $O(V+E)$-class; the decision in practice is almost always about incremental-update patterns and what auxiliary information (member lists vs a fast connectivity check) the downstream consumer actually needs, not about which is "faster."
• Common mistake: assuming Union-Find handles deletions just because it handles insertions cheaply. The asymmetry (cheap merge, no cheap split) is the single most important practical trade-off and the one most likely to bite a design that assumed both operations were equally supported.
• If the downstream need is "list every member of every component," DFS/BFS gives that as a direct byproduct of the traversal; Union-Find gives it only after an additional $O(V)$ grouping pass over all nodes by final root, a cost that is easy to forget when comparing the two approaches only on their headline complexity.
• On a graph that is already required to be memory-resident as an adjacency structure for other parts of the system (routing, querying neighbors, rendering the topology), DFS/BFS effectively costs nothing extra in memory, since it reuses that existing structure; Union-Find would then be introducing a second, redundant representation purely to get a connectivity answer.

Direct answer

Union-Find (disjoint set union) maintains a partition of elements into disjoint sets and supports two operations: find(x), which returns a representative (root) identifying which set x currently belongs to, and union(x, y), which merges the sets containing x and y into one. On its own, a naive version can degrade to $O(n)$ per operation on an adversarial sequence of unions, but adding path compression (flattening the tree toward the root during find) and union by rank or size (always attaching the smaller tree under the larger one) brings the amortized cost per operation down to $O(\alpha(n))$, the inverse Ackermann function, a value effectively bounded by 4 for every input size that could exist in practice. Two concrete infrastructure use cases: batching offline connectivity queries over a static snapshot of a network graph, and grouping servers or hosts into failure domains from a stream of "these two are on the same rack/switch/power circuit" observations.

Structured elaboration

The two operations in detail:

• find(x): walk x's parent pointer chain up to the root (the node that is its own parent). With path compression, every node visited during this walk gets repointed to point more directly at the root (either straight to the root, or to its grandparent under "path halving"), so subsequent find calls on those same nodes are faster.
• union(x, y): call find on both, and if the roots differ, attach one root under the other. Union by rank tracks an upper bound on each tree's height and always attaches the shorter tree under the taller one (breaking ties arbitrarily and bumping the surviving root's rank); union by size does the analogous thing tracking subtree size instead of height. Both give the same asymptotic guarantee.

Why amortized cost is near-constant. Union by rank alone bounds any tree's height at $O(\log n)$, so even without path compression, each find is $O(\log n)$ worst case. Path compression alone also gives an amortized $O(\log n)$ bound. The combination of both is what produces the much stronger $O(\alpha(n))$ amortized bound (a result due to Tarjan, 1975): every find call that walks through a node also flattens that node's future lookups, and union by rank ensures that no tree is allowed to grow needlessly tall in the first place, so the "expensive" flattening work a find call does gets amortized (spread out) over all the future cheap lookups it enables.

Two infrastructure use cases:

1. Offline connectivity queries over a static graph. Given a fixed snapshot of a network topology (which hosts can reach which others through some set of links) and a batch of "are A and B in the same reachable group" queries, build the Union-Find structure once by unioning every known edge, then answer every query in near-constant time via two find calls and an equality check, instead of re-running a graph traversal per query.
2. Grouping resources by failure domain. Given a stream of pairwise "these two hosts share a failure domain" facts (same rack, same top-of-rack switch, same power distribution unit, same availability zone), union each pair as the facts arrive. The resulting sets are exactly the maximal failure domain groups, useful for placement decisions (spread replicas across different find roots to avoid correlated failure) and for blast-radius estimation during an incident (given one affected host, find its root and treat every other member of that set as at elevated risk).

Worked example

For a tiny illustration of the failure-domain use case: suppose 6 hosts and the observed co-location facts arrive in this order: (host1, host2) share a rack, (host3, host4) share a rack, (host2, host3) share a power distribution unit, (host5, host6) share nothing observed yet. After processing the three known facts, the disjoint sets are {host1, host2, host3, host4} and {host5} and {host6}, three failure domains, even though no single fact directly named host1 and host4 together. This transitive-merging behavior (the union of a union) is exactly what a manual "same rack" lookup table would miss without repeatedly re-deriving connectivity, and is what Union-Find gives you for free as facts accumulate.

Trade-offs and pitfalls

• Union-Find has no efficient "un-union." Once you have merged the failure domains for host2 and host3 based on a shared power distribution unit, there is no cheap way to later split them back apart if that fact turns out to be stale (the unit was decommissioned, hosts were physically moved). A structure that must support both merges and un-merges over time needs periodic rebuilds or a genuinely dynamic-connectivity data structure, a materially harder problem.
• Common mistake: treating Union-Find as if it directly answers "list every host in this failure domain." It answers "are these two in the same domain" and "how many domains are there" in near-constant time, but producing the actual member list of a given domain requires a separate $O(n)$ grouping pass over all elements by their final root, not a property of the structure itself.
• Common mistake: implementing find/union without EITHER optimization and assuming it is "fine because it is a small graph." On a pathological build order (facts arriving in a long chain, host1-host2, host2-host3, host3-host4, ...), an unoptimized version degrades to a linked list and each subsequent find costs $O(n)$, which matters even at moderate scale if the facts stream is large or adversarially ordered.
• Failure-domain grouping is a good fit for Union-Find specifically because facts only ever ADD information (a shared rack or shared power unit is discovered, not un-discovered, in the normal operating case); if the underlying use case instead needed to react to topology changes that REMOVE a shared-domain relationship, this technique alone would not be enough.

Direct answer

Implement the two DSU (disjoint set union) primitives, find with path compression and union with union by rank, then answer each connectivity query with two find calls: x and y are connected exactly when find(x) == find(y). Building the structure from k1 edges and then answering k2 queries costs $O((k_1 + k_2) \cdot \alpha(n))$ total, effectively linear in the number of edges plus queries, because each find/union call is amortized near-constant time regardless of how many queries follow.

Structured elaboration

Why process all edges before any query, rather than interleaving. If queries only need to reflect the FINAL state of the graph (all edges applied), building the DSU once from every edge and then answering every query against the completed structure is both simpler and no less efficient than interleaving, since Union-Find has no notion of "time" (there is no way to ask "were x and y connected after only the first 3 edges" without re-deriving that from a prefix of the edge list). If a query needs to know connectivity at a specific POINT in an edge stream (not just at the end), that is a fundamentally different, harder problem (offline dynamic connectivity).

Structure:

1. Initialize parent[i] = i and rank[i] = 0 for all n nodes.
2. For each edge (u, v), call union(u, v).
3. For each query (x, y), call connected(x, y), defined as find(x) == find(y), and collect the boolean result.

Why connected needs no special-casing. Because find always terminates at a canonical root regardless of how the tree got built, comparing two roots correctly answers connectivity even for nodes that were merged transitively through several unrelated-looking edges, and even for a node queried against itself (find(x) == find(x) is trivially true, correctly reporting a node connected to itself).

Worked example

from typing import List, Tuple

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

def answer_queries(n: int, edges: List[Tuple[int, int]], queries: List[Tuple[int, int]]) -> List[bool]:
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return [dsu.connected(x, y) for x, y in queries]

if __name__ == "__main__":
    n = 6
    edges = [(0, 1), (1, 2), (3, 4)]
    queries = [(0, 2), (0, 3), (4, 3), (5, 0)]
    result = answer_queries(n, edges, queries)
    print("n:", n, "edges:", edges)
    print("queries:", queries)
    print("results:", result)

Output:

n: 6 edges: [(0, 1), (1, 2), (3, 4)]
queries: [(0, 2), (0, 3), (4, 3), (5, 0)]
results: [True, False, True, False]

Trace by hand: edges build two components, {0,1,2} and {3,4}, with 5 left isolated. Query (0,2): both in {0,1,2}, True. (0,3): different components, False. (4,3): both in {3,4}, True. (5,0): 5 is a singleton, False. All four match the printed output.

Trade-offs and pitfalls

• This is exactly $O((V + k_1 + k_2) \cdot \alpha(n))$, effectively linear, whereas answering each query independently with a fresh BFS/DFS from x toward y would cost $O(k_2 \cdot (V+E))$, since each query would redo a full traversal. Union-Find's advantage here is specifically that it decouples the cost of BUILDING connectivity information from the cost of ANSWERING a query about it: build once, query many times cheaply.
• Common mistake: rebuilding the DSU per query, which defeats the entire point of the structure and degrades performance to the naive per-query traversal cost.
• Common mistake: forgetting that queries against a node index outside [0, n) will raise an IndexError with an array-backed DSU; production code accepting untrusted query input should validate node indices before calling find.
• If queries must reflect an intermediate state of the edge stream (not just the final state), this design is wrong; it silently gives an answer as though all edges are already applied, which is correct only when every query is meant to run against the fully-built graph, as this question specifies.

Direct answer

Compute connected components with a standard flood-fill: iterate over every node, and whenever you find one that has not been visited yet, run a breadth-first search (BFS) or depth-first search (DFS) from it, collecting every node it reaches into one component and marking all of them visited. Each node and each edge is touched a constant number of times across the whole run, so the total cost is $O(V + E)$ regardless of how many components exist. BFS and DFS both achieve this bound; the choice between them is about auxiliary space and recursion behavior, not correctness or asymptotic speed.

Structured elaboration

Algorithm, using BFS to avoid Python's recursion-depth limit on deep or path-like components:

1. Maintain a visited set and a components list.
2. For every node start in the graph (this loop is what correctly handles isolated nodes: a node with an empty neighbor list still gets its own singleton BFS run and becomes its own component):
   • If start is already visited, skip it.
   • Otherwise, start a new BFS from start, marking each node visited exactly once as it is discovered (not when it is dequeued), and append every node BFS reaches to a new component list.
3. Return the list of components.

Why mark visited at discovery, not at dequeue: if you wait to mark a node visited until you pop it from the queue, the same node can be pushed onto the queue multiple times by different neighbors before it is ever dequeued, which does not break correctness but does waste work and, in pathological dense graphs, can blow up the queue size well past $O(V)$. Marking at discovery keeps each node enqueued at most once.

Complexity. Time: $O(V + E)$, because the outer loop over all nodes is $O(V)$, and across the ENTIRE run (not per component) every edge is examined exactly twice for an undirected graph represented as an adjacency list, once from each endpoint, giving $O(E)$ total edge work. Space: $O(V)$ for the visited set and the BFS queue in the worst case (a single component containing all nodes).

BFS vs DFS choice here: DFS (recursive) is more compact to write but risks a stack overflow on a graph with a long path-shaped component, since Python's default recursion limit is 1000; an iterative DFS with an explicit stack avoids that but is not meaningfully simpler than BFS once you write it iteratively. BFS with a deque avoids the recursion-depth risk entirely and is the safer default for a function that has to run correctly on arbitrary, potentially adversarial input graphs.

Worked example

from collections import deque
from typing import Dict, List

def connected_components(adj: Dict[int, List[int]]) -> List[List[int]]:
    seen = set()
    comps = []
    for start in adj:
        if start in seen:
            continue
        comp = []
        q = deque([start])
        seen.add(start)
        while q:
            u = q.popleft()
            comp.append(u)
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        comps.append(sorted(comp))
    return comps

if __name__ == "__main__":
    # 7 nodes: {0,1,2} triangle, {3,4} edge, {5} isolated, {6} isolated
    adj = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3], 5: [], 6: []}
    comps = connected_components(adj)
    print("components:", comps)
    print("count:", len(comps))

Output:

components: [[0, 1, 2], [3, 4], [5], [6]]
count: 4

This confirms both required properties: the isolated nodes 5 and 6 correctly appear as their own singleton components (they are never silently dropped by only iterating over edges), and the return shape is a list of component member-lists, not just a count.

Trade-offs and pitfalls

• Space complexity is $O(V)$, not $O(V + E)$, for the traversal itself: the visited set and queue hold at most $V$ node entries total across the run. (The $O(V+E)$ figure describes the input adjacency structure's size, not the extra space this algorithm allocates on top of it.)
• Common mistake: only iterating over edges to find components, which silently drops isolated nodes (nodes with no adjacency-list entries at all, or an empty entry) because they never appear as an edge endpoint. The for start in adj outer loop over ALL nodes, not just edge endpoints, is what fixes this; if the adjacency map itself is only built from edges, isolated nodes must be seeded into it (with an empty neighbor list) before this function runs.
• Common mistake: recomputing reachability from scratch inside the loop instead of sharing one growing visited set, which turns an $O(V+E)$ algorithm into $O(V \cdot (V+E))$ by redoing work for every already-visited node.
• DFS's recursion-depth risk is real, not theoretical, for pipeline or production code accepting untrusted graph shapes: a component shaped like a long chain (a "path graph") recurses to a depth equal to its length, and Python's default limit of 1000 will raise a RecursionError on a chain of roughly that length or longer. BFS or an explicit-stack DFS avoids this entirely.