Как хранить граф с большим количеством вершин?

Question

[dalbio]

Например у меня есть граф в котором n=1e+5 вершин.Хранить его как матрицу m[n][n] мне не хватит памяти.Что тогда делать?

Answer 1

[Антон Жилин]

Например, vector<vector<pair<int, int>>>, где каждый внутренний vector<pair<int, int>> содержит рёбра, ведущие из вершины с соответствующим индексом, а каждая pair<int, int> - это пункт назначения и вес ребра.

Comments

[dalbio]

А как мне например добавить ещё 1 внутренний вектор?

[dalbio]

Ну например даны рёбра:
1 2
2 1
2 3
1 3
Как их считать в этот граф?

[Wataru]

dalbio,
Построить просто - для каждого ребра u,v делайте next[u].push_back(v);. Если граф неориентированный, то симметрично добавляйте u в вектор для v.
Сначала не забудте выделить сам вектор: next.resize(n+1);

[Антон Жилин]

dalbio, я предполагал, что рёбра имеют вес. Если рёбра не имеют вес, то достаточно vector<vector<int>>