Question in Dinic

Revision en1, by purple_dreams, 2017-08-08 22:32:23

In Dinic algorithm for maximum flow, we in dfs we write the function as

for(int &t = ptr[source]; t < neighbours of source ; ++t)

I read that ptr is an array used to make finding the blocking flow in O(m) rather than O(m2). Why does this work and what is the exact use of keeping the ptr array. How does this array work?

Tags maxflow, dinic

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English purple_dreams 2017-08-08 22:32:23 361 Initial revision (published)