diff --git a/contrib/shrink-revlog.py b/contrib/shrink-revlog.py
--- a/contrib/shrink-revlog.py
+++ b/contrib/shrink-revlog.py
@@ -56,7 +56,6 @@ def toposort_reversepostorder(ui, rl):
     visit = list(heads)
     visit.sort(reverse=True)
     finished = set()
-    suboptimal = 0
 
     while visit:
         cur = visit[-1]
@@ -65,16 +64,10 @@ def toposort_reversepostorder(ui, rl):
                 visit.append(p)
                 break
         else:
-            curparents = rl.parentrevs(cur)
-            if result and result[-1] != curparents[0]:
-                suboptimal += 1
-
             result.append(cur)
             finished.add(cur)
             visit.pop()
 
-    ui.note(_('%d suboptimal nodes\n') % suboptimal)
-
     return result
 
 def toposort_postorderreverse(ui, rl):
@@ -104,7 +97,6 @@ def toposort_postorderreverse(ui, rl):
     visit = list(roots)
     visit.sort()
     finished = set()
-    suboptimal = 0
 
     while visit:
         cur = visit[-1]
@@ -113,19 +105,10 @@ def toposort_postorderreverse(ui, rl):
                 visit.append(p)
                 break
         else:
-            # if cur is not the first parent of its successor, then the
-            # successor is a suboptimal node
-            if result:
-                succparents = rl.parentrevs(result[-1])
-                if succparents[0] != cur:
-                    suboptimal += 1
-
             result.append(cur)
             finished.add(cur)
             visit.pop()
 
-    ui.note(_('%d suboptimal nodes\n') % suboptimal)
-
     result.reverse()
     return result
 
@@ -259,6 +242,15 @@ def shrink(ui, repo, **opts):
     try:
         try:
             order = toposort(ui, r1)
+
+            suboptimal = 0
+            for i in xrange(1, len(order)):
+                parents = [p for p in r1.parentrevs(order[i])
+                           if p != node.nullrev]
+                if parents and order[i-1] not in parents:
+                    suboptimal += 1
+            ui.note(_('%d suboptimal nodes\n') % suboptimal)
+
             writerevs(ui, r1, r2, order, tr)
             report(ui, r1, r2)
             tr.close()