В списках смежности используется 3 массива ls, r, prev.

В ls[v] хранится номер последнего ребра с которым связана вершина v, r[i] будет хранить номер вершины на которую ведет ребро i, prev[i] хранит номер ребра с которым вершина v была связана до ребра i.

Реализация:

for (i = 1; i <= m; i++)	{
	cin>>v>>u;
	prev[i] = ls[v];
	ls[v] = i;
	r[i] = u;
}

m — кол-во ребер.

Легче всего, мне кажется, так делается (на с++):

vector <vector <int> > graph(MaxN);
while (M--){
cin >> u >> v;
--u, --v; // если нумерация с 1 начинается
graph[u].push_back(v);
graph[v].push_back(u);
}

Получается, что graph[v] будет хранить список вершин связанных с вершиной v. Вот код:

cout << "Vertex " << v << " connected with: ";
for (int i = 0; i < graph[v].size(); i++) {
cout << graph[v][i] << " ";
}

И вот собственно dfs():

void dfs(int v){
was[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
    int to = graph[v][i]; // to -- вершина, связанная с вершиной v
    if (!was[to])
       dfs(to);
  }
}

моё http://codeforces.me/blog/entry/5195 подробное объяснение на эту тему, если есть вопросы — задавай!