Задача о неориентированных графах
Ребят, учим на английском. Всем классом думаем, ничего в голову не приходит. Решили спросить у могучих русских :)
Измените представление неориентированного графа посредством списков смежности так, чтобы первое ребро в списке смежности любой вершины мож- но было бы удалить за фиксированное время. Напишите процедуру удаления первых ребер, инцидентным вершинам, используя новое представление спи- сков смежности. Подсказка: как сделать так, чтобы две ячейки, соответст- вующие ребру (i, j), могли быстро находить друг друга?
В списке смежности поиск так или иначе будет всегда за O(n), на то и есть список-смежности. Если памяти не жалко, то заводить надо матрицу-смежности здесь и доступ за константное время O(1). Или только довольствоваться амортизированным временем..
Нет таковых и небыло никогда.