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.
It's manually written linked list
It looks like
e[i]stores the vertex towards which thei-th edge points,ne[i]stores the index of the next edge in the adjacency list which has thei-th edge, andh[x]stores the index of the first edge in the adjacency list of vertexx(i.e. the head of the adjacency list ofx). The add operation is adding an edge fromxtoyin the adjacency list ofxand 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).