Graph Theory37 sections · 1633 units
Open in Course

Implementing in C++

Vectors to the rescue

How do you implement a "list of lists" in C++? You use std::vector. You use an array of vectors.

vector<int> adj[N]

This creates an array of NN separate vectors. Each vector adj[i] stores the neighbors of node ii. Initially, all vectors are empty. As you read edges from input, you push neighbors into the appropriate vectors. This structure gives you O(1)O(1) access to any node's neighbor list and O(1)O(1) amortized time to add edges.