Преобразовать неориентированный граф в двунаправленный граф

Question

Учитывая G = (V, E) связный, неориентированный граф. Есть ли способ преобразовать его в ориентированный граф в обоих направлениях между двумя ребрами. так что если есть A и B как вершина, то A-> B и B-> A должны существовать в ориентированном графе. Я хочу знать алгоритм для этого, чтобы я мог написать код для него. Я не могу думать об этом.

Answer 1

Быстрый способ представления графа с 10 узлами: представление списка смежности узла в виде набора.

set<int> G[10];

Затем просто выполните

for(int u = 0; u < 10; u++){    //for each node u
    for(int v : G[u]){          //for each node v where exists an edge (u → v)

        if(!G[v].contains(u)) G[v].insert(u);    //add the missing edge (v → u) 

   }
}

Сложность: O (V + E lg (V))

Если хотите, вы можете использовать unordered_set вместо set и сделать сложность O (V + E).