Five Graph Habits That Cost Australian Teams Points
Photo by Photo by Walls.io on Unsplash on Unsplash
Australian university contests have a habit of making graph problems look familiar. The statement mentions roads, grids, dependencies, or social networks; the team recognises the shape; someone says 'just BFS it'; and twenty minutes later the submission is timing out on a case that should not be possible. The issue is usually not that the team cannot do graphs. It is that the team has a favourite graph reflex and applies it before checking the actual constraints.
These are five graph patterns that show up in ICPC-style practice and local Australian contests, and that Monash squads keep underestimating. For each one, the aim is not just to solve the problem but to turn it into a reusable contest lesson.
1. Implicit grid graphs
Recognition cue: the statement gives a grid of cells, moves between adjacent cells, and asks for shortest path, reachability, or connected components. There is no explicit adjacency list.
The trap: treating the grid as a general graph and building edges for every cell. That is usually unnecessary and sometimes too slow in memory. The grid is already a graph. BFS or DFS over coordinates is O(rows × columns) with a visited array or a distance grid. If moves have different costs, the reflex should change: BFS is for unweighted moves; 0-1 BFS is for costs of 0 and 1; Dijkstra is for general non-negative weights. A team that reaches for Dijkstra on an unweighted grid is not wrong, just wasteful, and waste matters when the time limit is tight.
Complexity trap: forgetting that the number of states can be larger than the number of cells. If the problem tracks a direction, a key, or a remaining budget, the graph is the product of position and state. That product needs to be in the complexity estimate before coding.
Team discussion prompt: 'What is the state, and how many of them are there?' Ask every member to answer before anyone writes code. If the answers differ, the team has found the real problem.
2. 0-1 BFS
Recognition cue: shortest path where every edge weight is either 0 or 1. It appears in problems about teleporters, toggling costs, or moving between layers where one move is free.
The trap: using Dijkstra because it is safe. It is safe, but 0-1 BFS is simpler and faster when the weights really are binary. The implementation detail that catches teams is the deque rule: push 0-weight neighbours to the front, 1-weight neighbours to the back, and allow a node to be relaxed again if a shorter distance is found. A visited array that closes a node on first pop can be wrong if the team is not careful about stale entries.
Complexity trap: treating the deque as a queue and then wondering why the distance is not minimal. The invariant is not 'first in, first out'; it is 'the deque is ordered by distance'. If the team cannot state that invariant, they should use Dijkstra and accept the extra log factor.
Team discussion prompt: 'Can we prove the deque stays sorted?' A short proof on a whiteboard is worth more than three accepted submissions by luck.
3. DSU with rollback
Recognition cue: the problem asks about connectivity under additions and removals, or offline queries where an edge is active over an interval. Standard DSU handles additions beautifully and removals badly.
The trap: trying to delete from a DSU. Path compression is not reversible, so a DSU with rollback must use union by size or rank and no path compression. The team then needs a stack of changes: which parent changed, which size changed. Rollback means undoing to a previous checkpoint, not deleting an arbitrary edge.
Complexity trap: forgetting the log factor from union by size, or forgetting that rollback adds a stack cost. The pattern is usually paired with divide-and-conquer over time or a segment tree over time. If the team has not seen that pairing, the DSU rollback alone will not save the problem.
Team discussion prompt: 'What is the timeline, and which edges are alive when?' Draw the intervals before choosing the data structure. This is a strategy drill as much as a graph drill.
4. Functional graphs
Recognition cue: every node has exactly one outgoing edge. The statement might describe a company where each employee reports to one manager, or a set of switches where each points to another. The graph is a collection of cycles with trees feeding into them.
The trap: running a general cycle detection routine and hoping. Functional graphs have a simpler structure: each component has exactly one cycle. Teams often miss that the cycle can be found with visited states or with indegree peeling. The latter is useful when the problem asks for nodes that eventually reach a cycle.
Complexity trap: revisiting nodes across multiple traversals and turning O(n) into O(n²). Use a state array: unvisited, in-progress, done. Or peel indegrees to remove trees, leaving only cycle nodes.
Team discussion prompt: 'What does the graph look like after we remove all indegree-zero nodes?' This question turns a messy traversal into a structural insight.
5. Layered graphs and state expansion
Recognition cue: the problem has a small extra dimension: a key bitmask, a number of moves left, a colour, a parity, or a 'used coupon' flag. The original graph is small, but the state space is the graph times the flag.
The trap: building the expanded graph explicitly when it is not needed, or forgetting it entirely and running BFS on the original graph. The right move is usually to treat the state as a node and run BFS or Dijkstra on the product. The complexity is O(states × transitions), not O(nodes × edges).
Complexity trap: a bitmask of 20 keys gives about a million states. That is fine. A bitmask of 25 gives 33 million, which is usually not fine in a five-hour contest with other problems waiting. Estimate before coding.
Team discussion prompt: 'What is the smallest extra state we need, and what is the worst-case product?' If the product is too large, the team needs a different model, not a faster queue.
The reusable lesson
The common thread is that graph problems reward a clear statement of the state, the edge cost, and the invariant. Australian contest statements are often plain and a bit dry, which makes it easy to pattern-match too early. The Monash habit worth building is a thirty-second graph check before coding: What are the nodes? What are the edges? What are the weights? What is the state? What is the complexity? Teams that answer those five questions out loud lose fewer points to graphs they already know how to solve.