Задача по теории графов

[sanyacvpx]

Нужно решить упражение из книги авторов Кормен, Лейзерсон, Ривест и Штайн - Алгоритмы. Построение и анализ

Сначала в главе рассказывается, что мы представляем граф списком смежности. Каждый элемент массива Adj[u] - это связный список вершин, смежных с u.

Теперь в конце упражнение:
Предположим, что вместо связного списка каждый элемент массива Adj[u] представляет собой хэш-таблицу, содержащую вершины v, для которых вершина u смежна с v. Чему равно математическое ожидание времени определения наличия ребра в графе, если проверка всех ребер выполняется с одинаковой вероятность? Какие недостатки имеет данная схема? Предложите другие струкруты данных, которые позволят решать данную задачу. Имеет ли ваша схема преимущества или недостатки по сравнению с хэш-таблицами?