Сколько запросов нужно для проверки связности

Неориентированный граф на $N$ вершинах задан матрицей смежности $N\times N$. Требуется определить, связен ли он.

(a) Докажите, что даже рандомизированному классическому алгоритму нужно $\Omega(N^2)$ запросов к элементам матрицы.

(b) Постройте квантовый алгоритм с ограниченной ошибкой и $O(N^{3/2}\log N)$ запросами. Подсказка. Используйте поиск Гровера.

(c) Докажите квантовую нижнюю оценку $\Omega(N^{3/2})$. Можно использовать квантовую теорему противника Амбайниса. За более слабую оценку $\Omega(N)$ также даётся часть баллов.