グラフ
頂点と、その頂点どうしを連結する辺からなるデータ構造。データの持ち方はいくつかあるが、大きく分けると
隣接行列
隣接リスト
のどちらかで持つことになる。
なお、競技プログラミングでたまに見かける他のデータの持ち方としては、辺の配列を保持して、各頂点についてそこから出ている辺IDのリストを保持するというものもある。この場合、隣接頂点を引くときはint v = ...; for (int e : v.edges) { int u = edge[e] ^ v; ... }のように、各辺を端点のXORで記憶するというテクニックが使われたりする。