Algorithmica Notebook

Appearance

From Linear to Connected ​

You are here: Ch 2 (Data Structures) → Ch 3 (Graph Foundations) | Core Path

What You've Built ​

Everything so far has been about sequences and hierarchies. Data has lived on a number line or inside a rooted tree, and every element knew exactly where it sat: index 4, depth 3, left child of node 7.

You've also built containers that preserve invariants under updates. Segment trees answer range queries. DSU tracks connectivity. Priority queues serve minimums. Powerful tools—but they all assume your data has a position or a rank.

What happens when the real structure is a web instead of a line?

When Position Isn't Enough ​

Consider cities connected by roads, where the "next" city depends on which road you take. Or tasks with prerequisites, where you can't start B until A is done and you can't start A until C is done. Or friendships, chemical bonds, network cables, airline routes.

These are not sequences. They are webs. The moment you force a web into an array, you stop using the structure and start fighting it.

Try it. Take six cities connected by roads: A–B, A–C, B–D, C–D, D–E, E–F. Store this in an array. What's at index 0? A? Okay, but A connects to both B and C—there is no single "next element." You can represent it with an adjacency matrix or an adjacency list, but either way the model has already shifted to nodes and edges. At that point, you are already thinking about graphs.

You've Already Done Graph Algorithms ​

Here's the funny part: you've already done graph algorithms. You just didn't call them that.

Remember DSU from Chapter 2? Union-Find? You were answering the question "are nodes u and v connected?"—that's a graph question. Each union(u, v) adds an edge. Each find(u) traverses a path. The whole structure is a forest of rooted trees, which is just a special kind of graph.

DSU gave you connectivity. But it couldn't tell you the shortest path between two nodes, or whether the graph has a cycle, or in what order to process nodes so every prerequisite comes first.

For those, you need to actually traverse the graph—visit nodes, explore neighbors, track distances.

That is what BFS and DFS do. BFS is "process nodes level by level using a queue." DFS is "go as deep as possible, then backtrack using a stack or recursion."

If you've used a queue from Chapter 2, you can write BFS. If you've written recursive functions in Chapter 0, you can write DFS. The graph part isn't the hard part—the hard part is seeing that a problem is a graph problem in the first place.

Three Problems That Need Graph Thinking ​

A maze. You're in a grid. Some cells are walls, some are open. Find the shortest path from the top-left to the bottom-right.

Each cell is a node; each pair of adjacent open cells is an edge. No adjacency list to build—the grid is the graph. BFS gives you the shortest path in O(rows×cols), and no array-based technique from Chapters 0–2 can do that, because "shortest path through a maze" is inherently about connectivity, not sorting or prefix sums.

You might think: "Can't I just use DP on the grid?" Sometimes, yes—if movement is restricted to right and down. But the moment you allow all four directions, DP breaks. It needs a topological ordering, and a grid with free movement has cycles. BFS doesn't care. It just explores.

Task scheduling. You have n tasks. Some depend on others: you can't compile until you've written the code, you can't test until you've compiled. Given all the dependencies, find a valid order to do the tasks—or report that it's impossible because of a circular dependency.

This is topological sorting on a directed acyclic graph (DAG). The dependency relationships form edges, and the topological order is the one where every edge points forward. DFS gives you this order as a byproduct—just record nodes in reverse finishing time. A back edge means a cycle, and the answer is "impossible."

No sorting algorithm from Chapter 1 can handle this. std::sort needs a comparison function between pairs of elements, but task dependencies aren't a total order. A might depend on B, C might depend on D, and there's no relationship between {A, B} and {C, D}. You need partial-order machinery, and that's exactly what topological sort provides.

Think about how you'd even represent this with Chapter 1–2 tools. You could store dependencies as pairs in an array and sort them somehow—but sort by what? There's no single key. The structure is relational, not positional. Model it as a graph—tasks as nodes, dependencies as directed edges—and the solution falls out naturally.

Network reliability. You have a network of servers connected by cables. If any single cable is cut, does the network stay connected? If not, which cables are critical?

These critical cables are called bridges, and finding them requires a DFS-based algorithm that tracks discovery times and back edges. The algorithm is subtle: maintain a timer that increments as DFS discovers new nodes, and track the lowest discovery time reachable from each subtree. When you find an edge whose subtree can't reach back above it, that edge is a bridge.

No amount of sorting, binary searching, or segment-tree querying will help here—this is purely about the structure of connections. The answer depends on the topology of the network: which paths exist, which alternate routes are available, where the bottlenecks are. That's graph territory.

The Conceptual Leap ​

A graph is just a generalization of the structures you already know. An array is a graph where node i connects to node i+1. A tree is a graph with no cycles. A grid is a graph where each node connects to its four neighbors. Even a linked list is a graph—one where every node has exactly one outgoing edge.

BFS and DFS are just "visit all elements"—like iterating through an array, but the neighbors aren't at index i±1. They're wherever the edges say they are.

If you can iterate an array, you can traverse a graph. Pick an unvisited element, process it, move to its neighbors. The only difference is that "neighbors" are now defined by edges rather than by arithmetic on indices. You already know iteration. You already know recursion. Graph traversal is just those two skills applied to a more general structure.

And the data structures from Chapter 2 come with you. BFS uses a queue. Dijkstra uses a priority queue. Kruskal's MST uses a DSU. You're not leaving tools behind—you're using them in a richer setting. Many graph algorithms are built from the structures you've already learned; they just orchestrate them differently.

What to Expect ​

Chapter 3 is where problems stop being about data and start being about relationships. The thinking changes. Instead of asking "what value is at position i?" you ask "what can I reach from here?" Instead of optimizing over a range, you optimize over a path.

Chapter 3 also introduces weighted graphs: edges that carry costs, distances, or capacities. That opens up shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) and minimum spanning trees (Kruskal, Prim). These are some of the most elegant algorithms in computer science, and they appear constantly in both contests and the real world.

It's a different way of seeing the world. And once you see it, you can't unsee it.

Before You Move On ​

Can you confidently:

  • [ ] Implement and use a segment tree for point updates and range queries?
  • [ ] Use DSU with path compression and union by rank?
  • [ ] Choose between a Fenwick tree and a segment tree for a given problem?
  • [ ] Use monotonic stacks and queues for "next greater" style problems?
  • [ ] Implement a priority queue and know when to use it over a set?
  • [ ] Recognize when a problem needs a data structure vs. a pure technique?

If any feel shaky, revisit Chapter 2. Graph algorithms build directly on these structures.

Key Files ​

Chapter 2 (just completed):

Chapter 3 (starting now):

Practice: Ladder: Graphs

Next: Chapter 3—Graph Foundations ​

Built for the climb from Codeforces 1100 to 2100.

Algorithmica Notebook