falling_frost's blog

Can't Understand the Meaning what this piece of code is doing . (HELP)
By falling_frost, 2 years ago, In English

ok, so I am working on a TREE problem and I encountered this piece of code and I am NOT able to understand what it is doing.

while taking the edges ( u-v ), it's going in a "add" function and the function is doing this :

void add(int x,int y) { e[idx]=y; ne[idx]=h[x]; h[x]=idx++; }

where idx is initialized to 0.

so my input was : 10 2 4 2 1 5 7 3 10 8 6 6 1 1 3 4 7 9 6

and after i print the 'e' , 'ne' , 'h' array:

e = 4 2 1 2 7 5 10 3 6 8 1 ne = -1 -1 0 -1 -1 -1 -1 -1 -1 -1 9 h = 0 12 2 13 14 4 17 15 8 16 7

totally confused.

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

Comments Comments (2)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's manually written linked list

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like e[i] stores the vertex towards which the i-th edge points, ne[i] stores the index of the next edge in the adjacency list which has the i-th edge, and h[x] stores the index of the first edge in the adjacency list of vertex x (i.e. the head of the adjacency list of x). The add operation is adding an edge from x to y in the adjacency list of x and updating the relevant data structures appropriately (storing the new edge, making a pointer to the next edge, and updating the head of the linked list).

→ Reply