Мне дают ориентированный мультиграф (граф, который может содержать самоконтроли и несколько ребер между двумя вершинами), и мне поручено преобразовать его в ориентированный простой граф (граф без самопетлей и только одно ребро, разрешенное междувершины) в O (V + E) времени и пространства.Мне дан список смежности для ориентированного мультиграфа, и я должен преобразовать его в другой список смежности для ориентированного простого графа.
Сначала я подумал опробежка по списку смежности G и прохождение каждого ребра через хеш-функцию в хеш-таблицу.Если бы были какие-либо столкновения, край не был бы сохранен.Затем, пройдя через каждое ребро, я бы преобразовал хеш-таблицу обратно в список смежности.Хотя это займет время O (V + E), для выделения хеш-таблицы потребуется больше места (O + V + E).
Может кто-нибудь объяснить, как они могут решить эту проблему?