Graph Storage & Traversal¶

In one sentence

Store, for every vertex, the list of its neighbours. Then walk the graph with DFS or BFS, marking what you have visited, and each walk visits exactly one connected component.

1. What problem does it solve?¶

Example — 217A · Ice Skating (6-DSU · E, rating 1200)

There are \(n\) snow drifts at distinct integer points \((x_i, y_i)\). From a drift, Bajtek can push off north, east, south or west and slide until he hits another drift. What is the minimum number of new drifts needed so he can get from any drift to any other?

Limits: \(n \le 100\), \(1 \le x_i, y_i \le 1000\).

Input   Output
2
2 1
1 2     1

2
2 1
4 1     0

Modelling. Two drifts on the same row (\(y_i = y_j\)) or the same column (\(x_i = x_j\)) can reach each other by sliding (possibly stopping at drifts in between, which is fine). So:

vertices = drifts,
edge between \(i\) and \(j\) when \(x_i = x_j\) or \(y_i = y_j\).

A group of drifts that can reach each other is a connected component (see Graph Concepts). With \(c\) components the answer is exactly \(c - 1\):

\(c - 1\) drifts are enough. A new drift at \((x_a, y_b)\), where \(a\) and \(b\) are drifts from two different components, shares a column with \(a\) and a row with \(b\), so it merges those two components. Repeat \(c - 1\) times.
Fewer are not. All drifts in one column are connected to each other, and so are all drifts in one row. A new drift lies in one column and one row, so it touches at most two components and lowers the count by at most \(1\).

First test: \((2, 1)\) and \((1, 2)\) share nothing, so \(c = 2\) and the answer is \(1\). Second test: both have \(y = 1\), so \(c = 1\) and the answer is \(0\).

So the real work is: count the components.

2. The ideas¶

2.1 Three ways to store a graph¶

Take this graph with \(n = 5\):

graph LR
  1 --- 2
  1 --- 3
  2 --- 3
  4 --- 5

storage	what it looks like	memory	"neighbours of \(u\)"	"is \((u, v)\) an edge?"
edge list	`[(1,2), (1,3), (2,3), (4,5)]`	\(O(m)\)	\(O(m)\), scan all	\(O(m)\)
adjacency matrix	`g[u][v] = 1` if connected, an \(n \times n\) table	\(O(n^2)\)	\(O(n)\)	\(O(1)\)
adjacency list	`adj[1] = [2, 3]`, `adj[2] = [1, 3]`, `adj[3] = [1, 2]`, `adj[4] = [5]`, `adj[5] = [4]`	\(O(n + m)\)	\(O(\deg u)\)	\(O(\deg u)\)
adjacency set	same, but `set()` instead of lists	\(O(n + m)\)	\(O(\deg u)\)	\(O(1)\) average

With \(n = 10^5\) a matrix needs \(10^{10}\) cells, which is impossible. Adjacency lists are the default. Switch to sets when edges get deleted or you must test "is \(v\) a neighbour?" often; the lesson notes below explain why. Ice Skating has only \(n = 100\), so any of them works.

2.2 Traversal: visit everything reachable¶

Both DFS and BFS follow one rule:

Start from \(s\) and mark it visited. Whenever you are at \(u\), go to every neighbour \(v\) that is not visited yet, and mark it.

Claim. Starting from \(s\), the walk visits exactly the vertices of \(s\)'s component, each once.

Only that component: we only ever move along edges, so everything we reach is connected to \(s\).
All of it: suppose some \(t\) connected to \(s\) is never visited. On the path \(s = v_0, v_1, \dots, v_k = t\), take the first unvisited vertex \(v_i\). Then \(v_{i-1}\) was visited, so when we processed \(v_{i-1}\) we looked at its neighbour \(v_i\) and would have visited it. Contradiction.
Once: the visited mark stops a second visit.

Cost. Each vertex is processed once, and processing \(u\) looks at its \(\deg(u)\) neighbours. By the handshake lemma, \(\sum \deg(u) = 2m\), so the total is \(O(n + m)\).

Counting components. Loop over all vertices; every time you find an unvisited one, add \(1\) and traverse from it. Each traversal marks one whole component, so the counter ends at \(c\).

2.3 DFS vs. BFS¶

	DFS (depth-first)	BFS (breadth-first)
goes	as deep as possible, then backs up	layer by layer: distance 1, then 2, …
uses	recursion, or a stack	a queue (`collections.deque`)
gives for free	tree structure, subtree sizes	shortest distances in unweighted graphs
Python risk	recursion depth (default limit \(1000\))	none

For "which vertices are connected", either works. In Python, BFS with a deque avoids recursion-limit crashes. Details on each: DFS, BFS.

Trace BFS from \(1\) on the picture above:

step	pop	new neighbours marked	queue after
start		\(1\)	`1`
1	\(1\)	\(2, 3\)	`2 3`
2	\(2\)	— (\(1, 3\) already visited)	`3`
3	\(3\)	—	empty

Component of \(1\) is \(\{1, 2, 3\}\). Next unvisited vertex is \(4\), so start again there: \(\{4, 5\}\). Two components.

3. Lesson notes — March 29¶

Recap¶

Today we continued learning graph theory in Python.

One important topic today was the adjacency list. If we want to delete an edge (u, v) from a graph, then in essence we need to delete v from the adjacency list of u, and also delete u from the adjacency list of v.

This naturally leads to a “why” question: why might set be a better choice than list in some graph problems?

If we use a list, then deleting a specific neighbor is often inconvenient and inefficient, because we may need to search through the whole list first. This is acceptable in some static graph problems, but it becomes awkward when the graph changes during the process.

In contrast, set is much more suitable when we need to add edges, delete edges, or quickly check whether a neighbor exists. So today we introduced set as an important Python tool for dynamic graph operations.

We also reviewed several important properties of trees:

A tree is connected.
A tree has no cycles.
A tree with \(n\) nodes has exactly \(n - 1\) undirected edges.

From these facts, we discussed an important related structure:

If a connected graph has \(n\) nodes and \(n\) edges, then it is a unicyclic graph. In other words, it contains exactly one cycle, and every other part of the graph can be viewed as a forest of trees attached to that cycle.

This is a very useful structure to recognize in graph problems.

Notes¶

Adjacency List¶

An adjacency list stores, for each node, which other nodes are directly connected to it.

For an undirected edge (u, v):

v should appear in the adjacency list of u
u should appear in the adjacency list of v

If we want to remove this edge, we must remove both entries.

Python `set`¶

A set is a collection of distinct elements.

Unlike a list, a set does not keep duplicates.

This makes it useful when we only care whether an element exists, rather than where it appears.

Example:

s = set()

You can also create a set from a list:

s = set([1, 2, 3])

Time Complexity: `list` vs `set`¶

Here are some common operations and their usual time complexities in Python:

Operation	`list`	`set`
Add one element	append: \(O(1)\) amortized	add: \(O(1)\) average
Delete one known value	\(O(N)\)	\(O(1)\) average
Check whether `x` exists	\(O(N)\)	\(O(1)\) average
Iterate through all elements	\(O(N)\)	\(O(N)\)
Get size with `len(...)`	\(O(1)\)	\(O(1)\)

This is the main reason set is attractive in graph problems with dynamic edge updates.

If we need to repeatedly add, delete, or test whether a neighbor exists, set is usually much more efficient than list.

Common `set` Operations¶

Add an Element¶

Use .add(x) to insert one element into a set.

s = {1, 2, 3}
s.add(4)
# s is now {1, 2, 3, 4}

If the element is already in the set, nothing goes wrong.

Remove an Element¶

Use .remove(x) to delete an element.

s = {1, 2, 3}
s.remove(2)
# s is now {1, 3}

Be careful: if x is not in the set, .remove(x) causes an error.

If you want a safer version, use .discard(x).

s = {1, 2, 3}
s.discard(5)
# no error

Check Whether an Element Exists¶

Use in to test membership.

s = {1, 2, 3}

if 2 in s:
    print("yes")

This is one of the most common uses of a set.

Iterate Through a Set¶

You can loop through all elements in a set.

s = {1, 2, 3}

for x in s:
    print(x)

Note that a set is unordered, so the output order is not guaranteed.

Get the Number of Elements¶

Use len(s).

s = {1, 2, 3}
print(len(s))

Clear the Set¶

Use .clear() to remove all elements.

s = {1, 2, 3}
s.clear()
# s is now set()

`set` in Graph Problems¶

If we store adjacency lists as sets, then each node keeps a set of its neighbors.

Example:

adj = [set() for _ in range(n + 1)]

To add an undirected edge (u, v):

adj[u].add(v)
adj[v].add(u)

To remove an undirected edge (u, v):

adj[u].remove(v)
adj[v].remove(u)

To check whether u and v are directly connected:

if v in adj[u]:
    print("connected")

This representation is especially useful when edges may be inserted or deleted during the problem.

Tree¶

A tree is a connected graph with no cycles.

Important properties:

A tree with \(n\) nodes has exactly \(n - 1\) edges.
There is exactly one simple path between any two nodes.

Unicyclic Graph¶

If a connected graph has \(n\) nodes and \(n\) edges, then it has exactly one cycle.

You can think of it as:

one cycle
plus several trees attached to nodes on that cycle

Recognizing this structure often makes graph problems much easier.

4. Worked solution — Ice Skating¶

Build the adjacency list from all pairs (\(n \le 100\), so \(n^2 = 10^4\) pairs is nothing), then count components with BFS.

import sys
from collections import deque

input = sys.stdin.readline


def solve():
    n = int(input())
    pts = []
    for _ in range(n):
        x, y = map(int, input().split())
        pts.append((x, y))

    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if pts[i][0] == pts[j][0] or pts[i][1] == pts[j][1]:
                adj[i].append(j)
                adj[j].append(i)

    visited = [False] * n
    components = 0

    for s in range(n):
        if visited[s]:
            continue
        components += 1

        visited[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)

    print(components - 1)


solve()

The same problem is also in the DSU set: union(i, j) for every connected pair, then count roots. See DSU.

5. Common mistakes¶

Marking visited when popping instead of when pushing

If you mark visited[v] only after popleft(), the same vertex can be pushed many times, which is slow and double-counts. Mark it when you push it, as above.

Recursive DFS on \(10^5\) vertices

A path graph \(1 - 2 - \dots - 10^5\) makes recursion \(10^5\) deep. Python's default limit is \(1000\). Use BFS, an explicit stack, or sys.setrecursionlimit plus care.

Forgetting isolated vertices

A vertex with no edges is its own component. Looping for s in range(n) catches it; looping only over edge endpoints does not.

Adding an undirected edge in one direction only

adj[i].append(j) without adj[j].append(i) makes BFS from \(j\) miss \(i\), and the component count comes out too big.

list.remove(v) to delete an edge

That is \(O(\deg)\) per deletion. If deletions are frequent, store neighbours in sets (see the lesson notes).

6. Practice¶

Problem	Set	Rating	Idea
217A · Ice Skating	6-DSU · E	1200	components (this page)
1676G · White-Black Balanced Subtrees	5-Graph · B	1300	DFS on a tree, count colours per subtree
1167C · News Distribution	6-DSU · B	1400	component sizes
277A · Learning Languages	6-DSU · A	1400	employees and languages as one graph
1833E · Round Dance	5-Graph · C	1600	components + degrees
1702E · Split Into Two Sets	5-Graph · D	1600	components must be even cycles

Credits & licenses

Storage comparison (§2.1): adapted and translated from OI Wiki — Graph Storage by Ir1d, sshwy, Xeonacid, partychicken, Anguei, HeRaNO and other OI Wiki contributors, licensed CC BY-SA 4.0.
Section structure follows USACO Guide — Graph Traversal by Siyong Huang, Benjamin Qi and Ryan Chou, licensed CC BY-NC-SA 4.0.
Everything else (the Ice Skating model, the correctness proof, traces, code, mistakes) is ours. §3 is our lesson recap.