Я обычно пользуюсь двумя способами представления графа, оба занимают O(V+E) памяти.
1. Просто создадим массив векторов размера V и в i-й вектор будем пихать вершины, смежные с i. Выглядит так:
vector<int> sm[10001];
...
sm[10].push_back(23);
...
Но этот способ не всегда хорош тем, что векторы долго инициализируются по сравнению со статическими массивами и еще операции с ними выполняются дольше. Я даже из-за времени инициализации в 2008 году на республиканской олимпиаде школьников потерял 100 баллов и взял 3 диплом 
2. Будем хранить граф в виде списка ребер, но хитро устроенного. Для каждой вершины заведем массив head, где будем хранить номер первого ребра в списке. Так же заведем массив ver, где в i-й ячейке будем хранить конец i-го ребра, а еще заведем массив nx, где для каждой ячейки где есть ребро будем хранить номер следующего ребра в списке. Выглядеть добавление ребра(если граф неориентированный, то будем добавлять еще и обратное ребро) будет так:
memset(head,-1,sizeof(head));
inline void add_edge(int v,int w)
{
ver[m]=w; nx[m]=head[v]; head[v]=m++;
ver[m]=v; nx[m]=head[w]; head[w]=m++;
}
Это был пример для неориентированного графа и если, к примеру, надо для ребра i узнать обратное, то номер у него будет i^1.
Чтобы пройти по всем смежным вершинам с v нужно написать что-то вроде:
for (int w=head[v];w>=0;w=nx[w])
{
cout<<ver[w]<<endl;
}