Matrix - The Problem

The Adjacency Matrix is fast for checking edges, but it has a huge flaw: Memory. It requires $N^2$ space.

If $N = 1000$, you need $1$ million cells. If $N = 100000$, you need $10$ billion cells. That exceeds typical memory limits. Most competitive programming graphs have $N$ up to $10^5$ or $10^6$ but only $M$ up to $10^6$ edges. Storing $N^2$ cells when you only have $M$ connections is wasteful. You need something more efficient for sparse graphs.