Representation, BFS/DFS & Components

A graph is a set of nodes and the edges between them. Almost every graph problem starts the same way: pick a representation, then walk it with DFS or BFS while a visited set stops you from going around in circles. Counting connected components (how many separate pieces the graph falls into) is the first thing you build on top of that walk.

Storing the graph#

You have two standard choices, and the decision almost always comes down to density: how many edges you have compared with the number of nodes.

	Adjacency list	Adjacency matrix
Shape	`adj[u]` = list of neighbors	`grid[u][v]` = 1 (or the weight)
Memory	$O(V + E)$	$O(V^2)$
Is `u`–`v` an edge?	$O(\text{degree})$ scan	$O(1)$
Best for	Sparse graphs (social networks, maps)	Dense graphs, or input already given as a matrix

Default to the adjacency list. Real data is sparse: you might have 500 friends on a social network with billions of users, and a matrix would store a row of billions of zeros for every user. Use a matrix only when most nodes are connected (so the $n^2$ space is justified) or the input already is a matrix.

For an undirected edge, add it in both directions (adj[u].append(v) and adj[v].append(u)). Forgetting the second line silently turns the graph into a directed one.

The idea#

Once the graph is stored, you walk it. DFS and BFS both visit every reachable node once. They differ only in the order, which comes from the container they use.

DFS ("the maze runner") goes as deep as it can, then backtracks. With recursion, the call stack remembers where you came from, so backtracking needs no extra code.
BFS ("a stone dropped in a pond") visits all neighbors at distance 1, then distance 2, and so on, using a FIFO queue. Because it expands in layers, the first time it reaches a node is along a path with the fewest edges.

Both need a visited set. Without it, if 0 connects to 1 and 1 connects to 0, the walk bounces between them forever. Each node is processed once and each edge is looked at a constant number of times, so both run in $O(V + E)$ .

Template#

Build an undirected adjacency list, then count components by starting a new walk from every node that no earlier walk reached. Either walk works inside the loop.

for each edge (u, v):
    add v to adj[u]; add u to adj[v]    # undirected: both ways
dfs(node):
    add node to visited
    for each nei in adj[node] not in visited: dfs(nei)
bfs(start):
    add start to visited; push start onto queue
    while queue is not empty:
        node = pop from the front of queue
        for each nei in adj[node] not in visited:
            add nei to visited          # mark on enqueue
            push nei onto queue
count = 0
for each node not in visited:
    walk from node; count += 1          # new walk, new component
return count

In BFS, mark a node visited the moment you enqueue it. If you wait until you pop it, two different parents can both add it to the queue, and the duplicate work grows with the number of edges.

How to spot it#

Problems rarely say "use BFS". The wording gives it away.

The question asks...	The graph is...	Use
Shortest path	Unweighted	BFS
	Weighted, non-negative	Dijkstra
	Has negative weights	Bellman-Ford (rare)
Connectivity	Edges keep arriving (merging)	Union-Find
	Fixed	DFS / BFS
Ordering	Dependencies	Topological sort
Connect everything cheaply	Weighted	MST (Kruskal)
Cycles	Undirected	Union-Find (or DFS with parent)
	Directed	Topological sort (or DFS)

When the graph is fixed and you only need to walk it, the wording also tells BFS and DFS apart:

BFS: "shortest path", "fewest steps", "minimum number of moves", "nearest", "level order". It guarantees the fewest hops in an unweighted graph.
DFS: "does a path exist?", "can we reach...?", "count all paths", "cycle detection", "topological sort", puzzle solving. It suits exhaustive searches that go deep and undo choices. It is not guaranteed to find the shortest path.

Memory: wide graphs vs deep graphs#

The two traversals remember different things, which matters on huge graphs. BFS holds the whole frontier (the current layer). DFS holds only the current path from the start.

Picture a star: one center node joined to 1,000,000 leaves. BFS pops the center and immediately queues all million leaves. DFS walks center → leaf → back, so its stack never holds more than two nodes.

Wide graph: BFS uses a lot of memory, so DFS is better.
Deep graph (a long chain): DFS's recursion stack grows with the depth, so BFS is safer. In Python this is also where you hit the recursion limit.

Connected components and input format#

How the input arrives can decide the complexity before you write any traversal.

An $n \times n$ matrix: you don't need to build a list. Walk straight on the matrix by scanning row node for 1s. Every visit scans $n$ columns, so the total is $O(n^2)$ , which is unavoidable because reading the input already costs that.
An edge list: building the list is $O(E)$ , and a walk visits each node once and each edge twice, so the total is $O(V + E)$ . You avoid the $O(n^2)$ scan.

Component counting also raises a question about the visited set: should every walk share it? It can be global (shared by every walk, as in component counting) or fresh for each search. A fresh one is needed when the relation is directed and you want the reach of each start on its own.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Adding an undirected edge in only one direction.
Marking visited on pop in BFS, which queues the same node many times.
Using DFS when the question asks for the fewest steps.
Recursion depth: a 10,000-node chain overflows Python's default recursion limit. Switch to an explicit stack or BFS.
Calling a relation symmetric when it isn't: check whether "a reaches b" implies "b reaches a" before adding both directions.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Number of Provinces

The input is already an $n \times n$ matrix. Walk on it directly by scanning row node for 1s, with no list to build. The total is $O(n^2)$ , the same as reading the input.

Hint: Number of Connected Components in an Undirected Graph

The input is an edge list, so build an adjacency list in $O(E)$ and count walks. The total is $O(V + E)$ .

Hint: Detonate the Maximum Bombs

Bomb i reaches bomb j when the squared distance is at most $r_i^2$ ; compare squares, no sqrt. The relation is directed: a big bomb can reach a small one that can't reach back. Run a separate walk with a fresh visited from every bomb, and take the largest count.

Hint: Count the Number of Complete Components

A complete component with $N$ nodes has $N(N-1)/2$ edges. Sum the degrees inside the component during the walk. Every edge counts twice, so the check is N * (N - 1) == degree_sum.

Hint: Clone Graph

Keep a map from each original node to its copy. One clean way is two passes: create a copy of every node, then wire each copy's neighbors through the map. Return the copy of the node you were given (copies[node]), never a fixed key such as "node 1". Space is $O(V + E)$ , because the copies carry every edge too.

Hint: Find the Town Judge

No traversal is needed, only in-degrees and out-degrees. The judge is trusted by everyone else and trusts no one, so one pass over the edges decides it.

Hint: All Paths From Source to Target

You need every path in a DAG (a directed graph with no cycles), so there is no visited set and no $O(V + E)$ bound. graph[node] is already an adjacency list. A DAG can have up to $2^{V-2}$ source-to-target paths, and copying each costs $O(V)$ , so time and space are $O(2^V \cdot V)$ .

Hint: Reconstruct Itinerary

You need a path that uses every ticket exactly once (an Eulerian path). Sort each airport's destinations, DFS by always taking the smallest unused one, and add an airport to the route only after all its edges are used. Reverse the route at the end.

Key takeaways#

Default to an adjacency list; use a matrix for dense graphs or when the input already is one.
DFS remembers the path, BFS remembers the frontier: wide graphs favor DFS, deep graphs favor BFS.
In BFS, mark visited when you enqueue.
Components = the number of times you have to start a new walk.
The input format can fix the complexity: an $n \times n$ matrix forces $O(n^2)$ .

Core idea#

Pick a graph representation, then walk it with DFS or BFS while a visited set stops cycles. Connected components are the number of times you start a new walk.

Key points#

Default to an adjacency list: $O(V + E)$ memory. Use a matrix for dense graphs or when the input already is one.
Add an undirected edge in both directions.
DFS goes deep and backtracks. BFS expands in layers with a FIFO queue and finds the fewest edges.
Both run in $O(V + E)$ .
In BFS, mark a node visited when you enqueue it, not when you pop it.
BFS holds the frontier, DFS holds the current path. Wide graphs favor DFS. Deep graphs favor BFS.
The input format can fix the cost. An $n \times n$ matrix forces $O(n^2)$ ; an edge list gives $O(V + E)$ .
Directed relations (Detonate the Maximum Bombs) need a fresh visited per start.

Which tool#

The question asks	Use
Fewest steps, unweighted	BFS
Shortest path, non-negative weights	Dijkstra
Connectivity as edges arrive	Union-Find
Ordering with dependencies	Topological sort
Connect everything cheaply	MST (Kruskal)

Template#

for each edge (u, v):
    add v to adj[u]; add u to adj[v]    # undirected
count = 0
for each start node not in visited:
    count += 1                          # new walk, new component
    add start to visited; push start onto stack
    while stack is not empty:
        node = pop from stack
        for each nei in adj[node] not in visited:
            add nei to visited; push nei onto stack
return count

Pitfalls#

Adding an undirected edge in one direction only.
Marking visited on pop in BFS. The same node enters the queue many times.
Using DFS when the question asks for the fewest steps.
A 10,000-node chain overflows Python's recursion limit. Use an explicit stack or BFS.

Say it in an interview#

"Adjacency list by default, because real graphs are sparse."
"Components equal the number of walks started from unvisited nodes."