sitingfake's blog

Can anyone help me?
By sitingfake, history, 14 months ago, In English

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 ?

  • Vote: I like it
  • +77
  • Vote: I do not like it

»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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>
→ Reply