Представление графа
Будем хранить граф в виде списка смежности. Список смежности в C++ удобно хранить в виде вектора векторов целых чисел (т.е. как vector<vector<int>>
). Иногда в качестве внешнего вектора используется массив. Размер внешнего вектора — количество вершин графа vertices, а i-я ячейка содержит список (вектор) всех вершин, которые смежны с i-й.
Следующий сниппет кода считывает неориентированный граф, в котором вершины были пронумерованы от 1:
cin >> vertices >> edges;
vector<vector<int>> g(vertices);
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}