The additional cost of \(O(m\log (n^2/m))\)  comes from the fact that,
at each level of the recursion, when a \(c\) -edge-connected component in \(S\)  splits into two components as a result of an edge deletion, we need to find edges of \(G\)  between these two components in order to update \(D\) .
This takes \(O(m\log {(n^2/m)})\)  total time throughout using a standard technique
of iterating through the edges incident to the nodes in the smaller component every time a split happens [1]}. The \(O(\log {(n^2/m)})\)  (instead of \(O(\log {(n)})\) ) cost comes by noticing that a vertex can at most have \(q\)  neighbors in a component of order \(q\) , and that after we go through the edges of a vertex \(i\)  times it is in a component of order \(\le n/2^{i}\) ; hence it is only the first \(O(\log (n/\deg (v)))\)  times that all neighbors of \(v\)  have to be considered, so the total time spent on this becomes \(O\left(\sum _{v\in V} \deg (v) \log (n/\deg (v)) \right)=O(m\log {(n^2/m)})\) .
