Блог пользователя sitingfake

Автор sitingfake, история, 14 месяцев назад, По-английски

Problem statement : there is a simple connected graph with n nodes , each node has a degree called d[i] construct a graph satisfy the request (the test show that there always has a solution), (n <= 10000)

i think there is a constructive algorithm and my solutions was trying to match the node with low to high degree, the first one i put all i with d[i] = 1 , in a stack called s[1] then i loop through 2 -> n, for(u : vertices with degree(i)) match with nodes in s[i] maximum with d[i] — 1 nodes , each nodes after match will decrease there degree and was pushed into s[i — 1] (i > 1) , after all trying to match all the stacks that are not empty together from high to low until all stacks are empty or there only s[1] still has some elements if so , i will make pairs between these i think that my solution was correct for the case this graph is a tree , however i think it's wrong for general graph , can u give me some idea ?

  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sitingfake (previous revision, new revision, compare).

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

For a general simple graph, you’d need something like the Havel–Hakimi algorithm (repeatedly connecting the highest-degree node to others, reducing degrees, and re-sorting) or an equivalent constructive method.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think you can implement this

Use a max heap, push all pair <d[i], i>

while (max_heap.size() > 1): 
  get <d[u], u> and <d[v], v> 
  connect u - v 
  d[u]--, d[v]-- 
  if d[u] > 0: push again <d[u], u>
  if d[v] > 0: push again <d[v], v>