🏠/Guides/Dsa Prep/Topic Guides/Graph Tricks
On this page

Graph Tricks

Graph Tricks — Codeforces Style

CF graph problems rarely give you explicit adjacency lists. You often need to build the graph from the problem statement.

1. Representation Choices

Type Best For Code
Adjacency List Most problems g [][]int
Edge List DSU, MST (Kruskal) []struct{u,v,w int}
Adj Matrix n ≤ 500, Floyd-Warshall dist [][]int
Implicit Grid Grid problems (4dir/8dir) Navigate with dx/dy arrays
Functional Virtual nodes, compressed graphs Build on the fly

2. DFS — Not Just Connectivity

func dfs(u, parent int) {
    visited[u] = true
    for _, v := range g[u] {
        if v == parent { continue }
        if visited[v] {
            // Found back-edge → cycle
        } else {
            dfs(v, u)
        }
    }
}

DFS Applications:

  • Cycle detection (in undirected: visited + not parent; in directed: 3-color: white/grey/black)
  • Topological sort (DFS finishing order reversed)
  • Bipartite check (alternating colors via DFS/BFS)
  • Bridge / articulation point (tin + low arrays — Tarjan)
  • Strongly Connected Components (Kosaraju / Tarjan)
  • Tree DP (DFS returns computed value)

3. BFS — Shortest Path on Unweighted

type Pair struct{ node, dist int }
func bfs(start int) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = -1 }
    q := []Pair{{start, 0}}
    dist[start] = 0
    for len(q) > 0 {
        cur := q[0]; q = q[1:]
        for _, v := range g[cur.node] {
            if dist[v] == -1 {
                dist[v] = cur.dist + 1
                q = append(q, Pair{v, dist[v]})
            }
        }
    }
    return dist
}

0-1 BFS (edges of weight 0 or 1)

Use deque — push 0-weight edges to front, 1-weight edges to back. O(V+E) instead of Dijkstra's O(E log V).

Multi-source BFS

Push all sources into queue initially. Set their dist = 0. Common for: nearest enemy position, fire spreading.

4. Dijkstra (Weighted Graph)

import "container/heap"

type Item struct { node, dist int }
type PQ []Item
func (h PQ) Len() int { return len(h) }
func (h PQ) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h *PQ) Push(x any) { *h = append(*h, x.(Item)) }
func (h *PQ) Pop() any { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }

func dijkstra(start int) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = math.MaxInt32 }
    pq := &PQ{}
    heap.Push(pq, Item{start, 0})
    dist[start] = 0

    for pq.Len() > 0 {
        cur := heap.Pop(pq).(Item)
        if cur.dist > dist[cur.node] { continue }
        for _, e := range g[cur.node] {
            nd := cur.dist + e.w
            if nd < dist[e.v] {
                dist[e.v] = nd
                heap.Push(pq, Item{e.v, nd})
            }
        }
    }
    return dist
}

Dijkstra Variants:

  • Path restoration — store prev[] array
  • Shortest path with constraints — add dimension (node, fuel_remaining, used_discount)
  • Meeting point — run Dijkstra from source and from destination, check midpoints

5. Floyd-Warshall (All Pairs, n ≤ 500)

for k := 0; k < n; k++ {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if dist[i][k] + dist[k][j] < dist[i][j] {
                dist[i][j] = dist[i][k] + dist[k][j]
            }
        }
    }
}

6. DSU (Disjoint Set Union / Union-Find)

type DSU struct {
    parent, size []int
}
func NewDSU(n int) *DSU {
    p := make([]int, n)
    s := make([]int, n)
    for i := range p { p[i] = i; s[i] = 1 }
    return &DSU{p, s}
}
func (d *DSU) Find(x int) int {
    for d.parent[x] != x {
        d.parent[x] = d.parent[d.parent[x]]  // path compression
        x = d.parent[x]
    }
    return x
}
func (d *DSU) Union(a, b int) bool {
    a, b = d.Find(a), d.Find(b)
    if a == b { return false }
    if d.size[a] < d.size[b] { a, b = b, a }
    d.parent[b] = a
    d.size[a] += d.size[b]
    return true
}

DSU tricks: - Reverse process (add edges instead of removing them) - DSU with rollback (store changes on stack, for offline dynamic connectivity) - DSU with size = number of elements (useful for counting connected components)

7. Minimum Spanning Tree (Kruskal)

func kruskal(edges []Edge, n int) int {
    sort.Slice(edges, func(i, j int) bool { return edges[i].w < edges[j].w })
    dsu := NewDSU(n)
    total := 0
    for _, e := range edges {
        if dsu.Union(e.u, e.v) { total += e.w }
    }
    return total
}

8. Topological Sort (Kahn's Algorithm)

func topoSort(g [][]int, indeg []int) []int {
    q := []int{}
    for i := 0; i < n; i++ { if indeg[i] == 0 { q = append(q, i) } }
    res := []int{}
    for len(q) > 0 {
        u := q[0]; q = q[1:]
        res = append(res, u)
        for _, v := range g[u] {
            indeg[v]--
            if indeg[v] == 0 { q = append(q, v) }
        }
    }
    return res
}

9. Grid Navigation Cheatsheet

// 4-direction
dx := []int{0, 0, 1, -1}
dy := []int{1, -1, 0, 0}

// 8-direction (knights + kings)
dx := []int{1, 1, -1, -1, 2, 2, -2, -2}
dy := []int{2, -2, 2, -2, 1, -1, 1, -1}

10. The "Suspicious" Graph Structures (CF Flavor)

Structure When How
Functional graph Each node has exactly 1 outgoing edge DFS + cycle detection, use indegree to find cycle nodes
Bipartite "Hate each other", "different groups" 2-color DFS
DAG from implicit order If a[i] < a[j] implies i→j Edges based on value comparison
Graph from array a[i] can go to i±a[i], or a[i] connects to a[j] if... Build edges according to rule
Virtual source/sink Multiple starting points, or connect all 0s to a single fake node Add node n+1, connect edges
Complement graph Original graph edges aren't important, but non-edges are Huge => use set for visited
Segment tree as graph DP needs range transitions (i → range of j) Build segment tree of virtual nodes

11. BFS on Complement Graph

When you need to traverse edges that represent the complement of a dense graph:

// Graph has edges (u, v) if they ARE NOT connected in original
// Use set of unvisited nodes
unvisited := make(map[int]bool)
for i := 0; i < n; i++ { unvisited[i] = true }

q := []int{0}
unvisited[0] = false
for len(q) > 0 {
    u := q[0]; q = q[1:]
    // Process all unvisited nodes not directly connected to u
    for v := range unvisited {
        if !hasDirectEdge(u, v) {  // complement edge
            q = append(q, v)
            delete(unvisited, v)
        }
    }
}

Runs in O(n + m) amortized using adjacency set for fast edge check.

← Previous
Dp Cf Patterns
Next →
Segment Tree
Graph Tricks