Graphs and Graph Algorithms Questions

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.

Direct answer

DFS coloring (white/gray/black) and recursion-stack detection are the same technique described two different ways: both mark a node as "currently on the active exploration path" the moment depth-first search (DFS) enters it, and unmark it the moment DFS finishes with it, so that an edge into a still-marked node is recognized as a back edge, a genuine cycle. Union-find (disjoint-set), by contrast, is fundamentally an UNDIRECTED-connectivity structure: it can only tell you "these two nodes are in the same component," never "is there a directed path from one back to the other," which is exactly what directed cycle detection actually requires, and applying it naively to a directed graph produces false positives on ordinary, acyclic shared-descendant structures.

Structured elaboration

DFS coloring, precisely. White means undiscovered. Gray means discovered and still being explored, equivalently, "on the current recursion stack." Black means fully finished, every node reachable from it has already been explored. When DFS at node $u$ examines an edge to neighbor $v$: white means recurse into $v$; gray means $v$ is an ancestor of $u$ on the current path, a back edge, a cycle; black means $v$ was already fully explored via some unrelated path, not a cycle.

Recursion-stack detection is the identical idea under a different name. Instead of three colors, maintain a boolean array inStack, set true when DFS enters a node and reset to false when DFS finishes with it (backtracks past it). "Gray" and "on the recursion stack" are the exact same set of nodes at every point in the traversal; the two formulations differ only in bookkeeping style (an enum-like color per node, versus a separate boolean array), not in what they detect or how.

Why union-find alone is insufficient for directed graphs. Union-find answers "are $u$ and $v$ already connected by SOME path, in either direction?" It has no notion of edge direction at all: union(u, v) merges two components regardless of which way the edge points. Consider the DIAMOND shape $0 \to 1$, $1 \to 3$, $0 \to 2$, $2 \to 3$: this is a perfectly acyclic DAG (directed acyclic graph), node 3 is simply a shared descendant of both 1 and 2. But processing these edges through undirected union-find: union(0,1), union(1,3), union(0,2) all succeed (new components merging), then union(2,3) finds find(2) and find(3) ALREADY in the same component (both merged in via 0-1-3 and 0-2 respectively) and reports a "cycle" that does not actually exist in the directed graph. Union-find cannot distinguish "these nodes are connected because of a legitimate shared ancestor/descendant" from "these nodes are connected because of an actual directed loop," because it discards direction entirely the moment an edge is unioned.

Worked example

Concise Python pseudocode sketch, DFS coloring:

def has_cycle(graph):
    color = {v: "white" for v in graph}
    def dfs(u):
        color[u] = "gray"
        for v in graph[u]:
            if color[v] == "white":
                if dfs(v):
                    return True
            elif color[v] == "gray":
                return True  # back edge -> cycle
        color[u] = "black"
        return False
    for node in graph:
        if color[node] == "white" and dfs(node):
            return True
    return False

if __name__ == "__main__":
    dag = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("DAG (no cycle):", has_cycle(dag))

    cyclic = {0: [1], 1: [2], 2: [0]}
    print("cyclic:", has_cycle(cyclic))

    self_loop = {0: [0]}
    print("self-loop:", has_cycle(self_loop))

    parallel_edges = {0: [1, 1], 1: []}
    print("parallel edges, no cycle:", has_cycle(parallel_edges))

    diamond_no_cycle = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("diamond shared descendant, no cycle:", has_cycle(diamond_no_cycle))

Output (actually executed with python3):

DAG (no cycle): False
cyclic: True
self-loop: True
parallel edges, no cycle: False
diamond shared descendant, no cycle: False

And, isolating the union-find false-positive claim specifically, running the diamond's edges through a plain, undirected union-find:

class UF:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.p[ra] = rb
        return True

edges = [(0, 1), (1, 3), (0, 2), (2, 3)]  # the same acyclic diamond DAG
uf = UF(4)
false_positive = any(not uf.union(u, v) for u, v in edges)
print("Union-find (undirected) falsely flags this acyclic diamond DAG as cyclic:", false_positive)

Output (actually executed with python3):

Union-find (undirected) falsely flags this acyclic diamond DAG as cyclic: True

This is a direct, executed confirmation of the claim: the exact same diamond shape that DFS coloring correctly reports as acyclic (False above) is INCORRECTLY reported as cyclic by naive undirected union-find, which is precisely why union-find alone cannot be used for directed cycle detection.

Edge cases

• Self-loops: an edge $u \to u$ is caught immediately, since $u$ is still gray (it just entered) when its own edge is examined; no special-casing is needed, though a caller who wants to deliberately IGNORE self-loops (treat them as valid, common in some dependency-graph conventions) needs to explicitly skip v == u before the color check.
• Parallel edges (multiple edges between the same ordered pair): correctness is unaffected, since a repeated edge to an already-black or already-white neighbor is evaluated the same way each time; the only cost is wasted iteration if the neighbor list contains true duplicates, worth de-duplicating at ingestion if the graph is expected to have many.

Trade-offs and pitfalls

• Common mistake: reaching for union-find on a directed cycle-detection task because it "worked for undirected cycle detection," without checking whether direction actually matters for the graph at hand; the diamond example above is exactly the shape that exposes this mistake in the smallest possible test case, and is worth keeping as a permanent regression test for any codebase where this confusion has happened once.
• Common mistake: implementing recursion-stack detection with a SHARED inStack array across multiple independent DFS calls (from different starting nodes in the same traversal) but forgetting to reset it correctly on backtrack, which can cause a node correctly finished and popped off one branch's stack to be mistaken for still being on-path when a completely different branch later reaches it.
• When union-find IS the right tool. For UNDIRECTED cycle detection specifically (does an undirected graph, as opposed to a directed one, contain a cycle), union-find is both correct and often simpler than DFS with parent-tracking, since undirected connectivity is exactly what it was built to answer; the insufficiency here is specific to the directed case, not a general weakness of the data structure.
• Performance. Both DFS-based techniques are $O(V+E)$; union-find with path compression and union by rank is $O(E \alpha(V))$ for the undirected case it is actually suited to, effectively linear, so there is no performance argument for reaching past DFS coloring toward union-find on a directed graph, only a correctness argument against doing so.

Direct answer

An implicit graph never materializes its full node or edge set up front: neighbors are computed on demand by calling produce_neighbors(state), and breadth-first search (BFS) still applies unmodified, since BFS only ever needs "give me the neighbors of this node right now," never the whole graph at once. This is exactly what a state-space search (a puzzle, a game position, an abstract configuration space) needs, since materializing every reachable state ahead of time is often impossible or wasteful.

Structured elaboration

Why BFS still guarantees shortest path here. BFS's core guarantee, the first time a state is discovered it is at its true minimum distance, depends only on exploring states in non-decreasing distance order, never on knowing the graph's shape in advance. Calling produce_neighbors lazily, one node at a time, preserves this exactly: each call happens precisely when that node is dequeued, in the same layer-by-layer order BFS always uses.

Pruning strategies. A visited set is the baseline prune (never re-expand a state already discovered), but implicit graphs often support domain-specific pruning too: reject a neighbor immediately if it violates an invariant (an illegal board position, a state outside a known-safe region) before it is ever added to the queue, saving both the memory to store it and the future work of expanding it. Pruning by domain invariant must never prune a state that could still be on SOME shortest path, or the "shortest" guarantee breaks; a prune based purely on redundancy (already visited) is always safe, a prune based on heuristic judgment is not automatically safe unless proven admissible.

Heuristics. If a heuristic estimate of remaining distance to the goal is available, switching from plain BFS to A* (using the heuristic to prioritize which state to expand next via a priority queue instead of a FIFO queue) can dramatically reduce the number of states visited, at the cost of losing BFS's simplicity and requiring the heuristic to be admissible (never overestimate the true remaining distance) to keep the shortest-path guarantee.

Bidirectional search. When both start and goal are known in advance (not always true in state-space search, but common), growing frontiers from both ends and stopping when they meet bounds the search to roughly the square root of the single-direction node count for a typical branching factor, the same principle as bidirectional BFS on any explicit graph.

Worked example

from collections import deque
from typing import Callable, Iterable, List, Optional, TypeVar

State = TypeVar("State")

def find_shortest_sequence(start: State, goal: State,
                            produce_neighbors: Callable[[State], Iterable[State]]) -> Optional[List[State]]:
    if start == goal:
        return [start]
    parent = {start: None}
    q = deque([start])
    while q:
        s = q.popleft()
        for nxt in produce_neighbors(s):
            if nxt in parent:
                continue
            parent[nxt] = s
            if nxt == goal:
                path = [nxt]
                cur = nxt
                while parent[cur] is not None:
                    cur = parent[cur]
                    path.append(cur)
                return list(reversed(path))
            q.append(nxt)
    return None

if __name__ == "__main__":
    # Abstract 12-state space: from state s, neighbors are s+1, s-1, s+5 (mod 12).
    # Deliberately not a literal grid or puzzle, to make the point that BFS
    # does not care what a "state" actually represents.
    N = 12
    def produce_neighbors(state):
        return [(state + 1) % N, (state - 1) % N, (state + 5) % N]

    path = find_shortest_sequence(0, 7, produce_neighbors)
    print("Shortest sequence 0 -> 7:", path)
    print("Steps:", len(path) - 1 if path else None)

    def is_valid(path, produce_neighbors):
        return all(path[i+1] in set(produce_neighbors(path[i])) for i in range(len(path)-1))
    print("Path uses only real transitions:", is_valid(path, produce_neighbors))

    def full_bfs_dist(start, produce_neighbors):
        dist = {start: 0}
        q = deque([start])
        while q:
            u = q.popleft()
            for v in produce_neighbors(u):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    ref = full_bfs_dist(0, produce_neighbors)
    print("Matches independent full-BFS distance table:", ref[7] == len(path) - 1)

    print("No path from a state that only transitions to itself:", find_shortest_sequence(100, 200, lambda s: [s]))

Output (actually executed with python3):

Shortest sequence 0 -> 7: [0, 1, 2, 7]
Steps: 3
Path uses only real transitions: True
Matches independent full-BFS distance table: True
No path from a state that only transitions to itself: None

The independent full_bfs_dist helper computes distances to every reachable state from scratch, without reusing the path-returning function's logic, and its distance to state 7 (3) matches len(path) - 1 exactly, confirming the lazily-called produce_neighbors version is genuinely finding a true shortest sequence, not just any sequence.

Complexity

Time $O(N + E)$ where $N$ is the number of reachable states and $E$ is the number of transitions actually explored (both unknown in advance for a true implicit graph, unlike an explicit one where $V$ and $E$ are given). Space $O(N)$ for parent and the queue. Each call to produce_neighbors is charged whatever it costs to compute (in the example above, $O(1)$; in a real puzzle, it might be proportional to board size).

Edge cases

• start == goal: returns [start] immediately, a zero-move sequence, without ever calling produce_neighbors.
• No path exists (as demonstrated by the self-loop-only state 100 in the worked example): the queue drains completely, parent never gains an entry for goal, and the function returns None.
• produce_neighbors yielding a state already on the current path (a state with a transition back to itself, or a cycle in the state graph): handled the same as any other implicit-graph cycle, since the parent dict doubles as the visited set, a state already discovered is never re-enqueued.
• produce_neighbors raising an exception mid-search (a real risk if computing a state's neighbors can fail, for example an invalid board configuration): not handled by the implementation above, and worth flagging explicitly as something a production version would need to decide on: abort the whole search, or treat that state as having no valid neighbors and continue.

Trade-offs and pitfalls

• Common mistake: calling produce_neighbors more than once for the same state (for example, once to check if any neighbor is the goal, and again to actually enqueue them). Since neighbor generation can be expensive in a real state space, the implementation above calls it exactly once per dequeued state and processes each yielded neighbor as it arrives.
• Common mistake: pruning by a heuristic that is not admissible (can overestimate true remaining distance), which silently breaks BFS's shortest-path guarantee; a state that gets pruned because it "looks unpromising" might still sit on the actual shortest path.
• Infinite or unbounded state spaces. Unlike a finite explicit graph, an implicit state space can be infinite (an unbounded counter, an open-ended configuration). Plain BFS on such a space either runs forever if goal is unreachable, or needs an explicit depth cap or iterative-deepening strategy layered on top to guarantee termination even on a "no path exists" input.
• When to reach for A instead.* If a genuinely admissible heuristic exists (an under-estimate of remaining distance that is cheap to compute), A* dominates plain BFS by visiting fewer states while preserving the same shortest-path guarantee; if no such heuristic is available or trustworthy, plain BFS remains the safe default.

Direct answer

An adjacency list stores, for each vertex, the list of its neighbors; it is compact for sparse graphs and is the default choice for most traversal algorithms. An adjacency matrix stores a $V \times V$ grid where entry $(u,v)$ marks whether an edge exists; it gives constant-time edge lookups at the cost of $O(V^2)$ space regardless of how many edges actually exist. The right choice comes down to density: pick the list when edges are far fewer than $V^2$ (the common case), pick the matrix when the graph is small and dense or when O(1) edge-existence checks dominate the workload.

Structured elaboration

Operation costs ($V$ = number of vertices, $E$ = number of edges, $\deg(u)$ = out-degree of $u$):

Directed vs undirected. For a directed graph, add/remove touch one entry. For an undirected graph, both representations must update the entry in both directions, $(u,v)$ and $(v,u)$, so the constant factor doubles but the complexity class does not change.

Space. Adjacency list: $O(V + E)$ for a directed graph, or $O(V + 2E)$ for undirected since each edge is stored once per endpoint (still $O(V+E)$ asymptotically, since $2E = O(E)$). Adjacency matrix: $O(V^2)$ always, independent of how many edges are actually present.

Worked example

Graph A: V = 100,000, E = 200,000.
Adjacency list needs roughly $V + E = 300{,}000$ entries (directed) or $500{,}000$ (undirected), a few megabytes either way. The matrix needs $V^2 = 10^{10}$ entries. Even at 1 bit per entry that is $10^{10}/8 \approx 1.25 \times 10^{9}$ bytes, about 1.16 GiB, and at 1 byte per entry it is about 9.3 GiB. Those numbers are not literally impossible to allocate on a large machine, but the graph's own density (at most $E / [V(V-1)] \approx 2.0 \times 10^{-5}$, about 0.002%, if directed) means over 99.99% of the matrix's cells would encode "no edge." Adjacency list wins: same information in roughly 30,000x less space, with no capability lost for this workload.

Graph B: V = 10,000, E = 80,000,000. Before recommending anything, check whether this edge count is even achievable. The maximum number of edges in a simple undirected graph on 10,000 nodes is $V(V-1)/2 = 49{,}995{,}000$, which is less than the stated 80,000,000. So this graph can only be realized as directed (max $V(V-1) = 99{,}990{,}000$, and 80,000,000 is about 80% of that, a genuinely dense digraph) or as a multigraph with parallel edges. Treating it as directed: adjacency matrix needs $V^2 = 10^8$ entries, 100 MB at 1 byte per entry or 12.5 MB at 1 bit per entry. Adjacency list needs $O(V+E) \approx 80{,}010{,}000$ entries; even at a compact 4 bytes per neighbor id that is roughly 320 MB, several times larger than the byte-per-entry matrix. With the graph 80% full, most rows are nearly complete anyway, so the matrix's $O(V)$ neighbor scan is not wasteful in practice. Recommendation: adjacency matrix for Graph B, adjacency list for Graph A.

Role-flavored variants of the same reasoning: a social-network adjacency graph (most users have a small, bounded number of connections relative to the total user count) is sparse like Graph A and belongs in an adjacency list, typically backed by hash sets so mutual-friend checks are O(1). A backend service's topology graph (which services call which) is usually small enough in vertex count that either representation fits in memory, but teams default to adjacency lists because service graphs are edited far more often than they are queried for raw connectivity. A machine learning engineer's graph choice usually tracks the same density argument: a sparse knowledge graph or citation graph behaves like Graph A, while a dense similarity graph or attention-weight graph over a small batch can behave like Graph B.

Trade-offs and pitfalls

• Dynamic graphs. Adjacency lists (especially backed by hash sets) handle frequent insert/delete well. Matrices give O(1) point updates but are expensive to grow, resizing $V$ means reallocating an entire $O(V^2)$ structure.
• Compressed sparse row (CSR). Stores the graph as two flat arrays: an offsets array of size $V+1$ and a flattened neighbor array of size $E$. Same $O(V+E)$ space as a list but contiguous memory, which gives far better cache locality when iterating neighbors repeatedly (as BFS/DFS/Dijkstra do). The cost is mutation: inserting one edge into a CSR structure generally requires rebuilding the offsets array, so CSR fits static or mostly-read graphs, not graphs under constant edit.
• Edge list. Stores raw $(u, v[, w])$ tuples, $O(E)$ space, minimal overhead. Good for streaming ingestion and for algorithms that consume edges directly in some order (Kruskal's minimum spanning tree sorts the edge list by weight). Bad for neighbor iteration or existence checks unless you build an index on top.
• Common mistake: assuming a plain adjacency list gives O(1) edge-existence checks. A bare list of neighbors gives $O(\deg(u))$; you only get O(1) by paying for a hash set per vertex, which costs more memory and constant-factor overhead than a plain dynamic array.
• Common mistake: picking a representation from a size label ("small graph" or "big graph") instead of computing the actual density. Graph B above looks intimidating at 80 million edges, but relative to its 10,000 nodes it is a dense graph that a matrix handles comfortably; a habit of always reaching for adjacency lists would have picked the wrong tool here.

Direct answer

An articulation point (cut vertex) is a node whose removal increases the number of connected components in the graph; a bridge (cut edge) is an edge whose removal does the same. Both are found in a single depth-first search (DFS) pass using the "low-link" technique: track each node's discovery time and its low-link value (the earliest discovery time reachable from that node's DFS subtree via at most one back edge), and a node/edge is flagged as critical based on how a child's low-link compares to the current node's own discovery time. In a network topology, these are exactly the single points of failure: an articulation point is a device whose failure partitions the network, and a bridge is a link whose failure does the same, both directly actionable signals for where redundancy is most needed.

Structured elaboration

Discovery time and low-link, defined precisely. disc[u] is the order in which DFS first visits u (a simple counter incremented on each new visit). low[u] starts equal to disc[u] and is then lowered to the minimum discovery time reachable from u's subtree by following tree edges down and at most one back edge up past u itself; concretely, low[u] = min(low[u], disc[v]) for every back edge to an already-visited (non-parent) node v, and low[u] = min(low[u], low[v]) after fully exploring each tree-edge child v.

Articulation point condition. For a non-root node u with DFS-tree child v: u is an articulation point if low[v] >= disc[u], meaning v's entire subtree cannot reach back to any ancestor of u (not even u itself, in the strict inequality case) without going back through u, so removing u would strand that subtree. The ROOT of a DFS tree is a special case, handled separately: it is an articulation point exactly when it has more than one child in the DFS tree, since each such child's subtree is only connected to the rest of the tree through the root.

Bridge condition. For a tree edge (u, v) where v is u's child: (u,v) is a bridge if low[v] > disc[u] (strict inequality, unlike the articulation-point condition), meaning v's subtree has NO way back to u or any ancestor of u at all, not even to u itself via some other path, so this specific edge is the only connection.

Why single points of failure matter operationally. In a network topology, both articulation points and bridges directly identify where a SINGLE failure (one device down, or one link down) causes a partition, not merely a slowdown; this is qualitatively different from and more urgent than general redundancy planning, since it names the EXACT minimal set of failures that would split the network, which is the natural prioritization list for where to add redundant links or failover devices first.

Worked example

from typing import Dict, List, Set, Tuple

def find_articulation_points_and_bridges(graph: Dict[int, List[int]]):
    disc, low = {}, {}
    visited = set()
    timer = [0]
    articulation_points: Set[int] = set()
    bridges: List[Tuple[int, int]] = []

    def dfs(u, parent):
        visited.add(u)
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in graph.get(u, []):
            if v == parent:
                continue
            if v in visited:
                low[u] = min(low[u], disc[v])
            else:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent is not None and low[v] >= disc[u]:
                    articulation_points.add(u)
                if low[v] > disc[u]:
                    bridges.append((min(u, v), max(u, v)))
        return children

    for start in graph:
        if start not in visited:
            root_children = dfs(start, None)
            if root_children > 1:
                articulation_points.add(start)

    return sorted(articulation_points), sorted(bridges)

if __name__ == "__main__":
    # Network: two triangles (0-1-2) and (3-4-5) joined by a single bridge edge 2-3,
    # plus a pendant node 6 hanging off node 5.
    graph = {
        0: [1, 2], 1: [0, 2], 2: [0, 1, 3],
        3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [5],
    }
    ap, bridges = find_articulation_points_and_bridges(graph)
    print("articulation points:", ap)
    print("bridges:", bridges)

Output:

articulation points: [2, 3, 5]
bridges: [(2, 3), (5, 6)]

By inspection: removing node 2 disconnects {0,1} from the rest, so it is an articulation point; removing node 3 disconnects {0,1,2} from {4,5,6}; removing node 5 disconnects {6}; the edges (2,3) and (5,6) are each the sole connection to a piece of the graph and so are bridges. All four match the executed output exactly.

Trade-offs and pitfalls

• The articulation-point and bridge CONDITIONS differ by a single inequality (>= versus >), and mixing them up is the single most common implementation bug: using > for the articulation-point check would wrongly exclude u when low[v] == disc[u] (a case where v's subtree CAN reach back exactly to u, but no further, meaning removing u still strands the subtree, so u genuinely is an articulation point despite the border case).
• The root of the DFS tree needs separate handling entirely, since the general non-root formula (low[v] >= disc[u]) does not apply to a node with no parent to be "cut off from"; a root is only critical if it has more than one DFS-tree child, since those children's subtrees are then only interconnected THROUGH the root.
• A node can be an articulation point without any single INCIDENT edge being a bridge, and vice versa is also possible; the two concepts overlap but are not equivalent, and a network engineer reading these results needs both lists, not just one, to fully understand the topology's fragility.
• This algorithm assumes an undirected, simple graph (the if v == parent: continue check specifically handles the back-and-forth of a single tree edge, but does not correctly handle true parallel/multi-edges between the same pair of nodes); a network topology with genuine redundant parallel links between two devices needs the algorithm adjusted to track edge identity, not just endpoint identity, or a duplicate parallel edge would be incorrectly treated as a back edge to the immediate parent and silently ignored.