{"algorithm":"gabow","about":["Gabow's algorithm finds the strongly connected components in one depth-first search, as Tarjan's does, but without lowlink values. It keeps two stacks. The first holds the vertices the search has reached that aren't in a component yet. The second holds the vertices on the current path that could still be the first vertex of a component.","When an edge leads to a vertex still on the first stack, every vertex on the path after it is in the same component, so the second stack is popped back to it. When the search finishes a vertex that is still on top of the second stack, that vertex starts a component. The first stack is popped down to it, and those vertices form the component.","It costs O(V+E). On the same graph, Tarjan's and Gabow's algorithms find the same components in the same order. They differ only in how they tell that the search has finished one."],"template":{"id":"linked-pages","name":"Linked web pages","description":"Forty pages of a product website, P1 to P40, where P stands for page: the main site (P1 to P13), the blog (P14 to P19), landing pages (P20 to P24), the help center (P25 to P28), the docs (P29 to P38) and the status pages (P39 and P40). Each edge counts the links from one page to another. Only ads and emails lead to the landing pages, and the help center, docs and status pages never link back to the main site.","family":"cyclic","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"P1","x":225,"y":687},{"id":"P2","x":134,"y":683},{"id":"P3","x":239,"y":604},{"id":"P4","x":206,"y":763},{"id":"P5","x":112,"y":601},{"id":"P6","x":312,"y":664},{"id":"P7","x":103,"y":760},{"id":"P8","x":200,"y":532},{"id":"P9","x":288,"y":782},{"id":"P10","x":40,"y":650},{"id":"P11","x":327,"y":576},{"id":"P12","x":157,"y":836},{"id":"P13","x":105,"y":516},{"id":"P14","x":324,"y":298},{"id":"P15","x":258,"y":341},{"id":"P16","x":189,"y":305},{"id":"P17","x":185,"y":228},{"id":"P18","x":250,"y":185},{"id":"P19","x":320,"y":221},{"id":"P20","x":483,"y":182},{"id":"P21","x":503,"y":107},{"id":"P22","x":580,"y":102},{"id":"P23","x":609,"y":174},{"id":"P24","x":549,"y":224},{"id":"P25","x":822,"y":255},{"id":"P26","x":840,"y":330},{"id":"P27","x":765,"y":349},{"id":"P28","x":746,"y":274},{"id":"P29","x":855,"y":670},{"id":"P30","x":777,"y":716},{"id":"P31","x":823,"y":592},{"id":"P32","x":881,"y":744},{"id":"P33","x":714,"y":658},{"id":"P34","x":916,"y":604},{"id":"P35","x":793,"y":797},{"id":"P36","x":751,"y":553},{"id":"P37","x":960,"y":715},{"id":"P38","x":680,"y":738},{"id":"P39","x":531,"y":898},{"id":"P40","x":506,"y":824}],"edges":[{"from":"P1","to":"P2","weight":2},{"from":"P1","to":"P3","weight":2},{"from":"P1","to":"P4","weight":1},{"from":"P1","to":"P6","weight":1},{"from":"P1","to":"P14","weight":1},{"from":"P1","to":"P29","weight":1},{"from":"P1","to":"P9","weight":3},{"from":"P1","to":"P10","weight":1},{"from":"P1","to":"P25","weight":1},{"from":"P1","to":"P39","weight":1},{"from":"P2","to":"P1","weight":1},{"from":"P2","to":"P3","weight":2},{"from":"P2","to":"P5","weight":1},{"from":"P2","to":"P9","weight":2},{"from":"P2","to":"P29","weight":1},{"from":"P3","to":"P1","weight":1},{"from":"P3","to":"P9","weight":3},{"from":"P3","to":"P8","weight":1},{"from":"P3","to":"P26","weight":1},{"from":"P3","to":"P11","weight":1},{"from":"P4","to":"P1","weight":1},{"from":"P4","to":"P17","weight":2},{"from":"P4","to":"P9","weight":1},{"from":"P5","to":"P2","weight":1},{"from":"P5","to":"P33","weight":2},{"from":"P6","to":"P1","weight":1},{"from":"P6","to":"P7","weight":2},{"from":"P6","to":"P8","weight":1},{"from":"P6","to":"P14","weight":1},{"from":"P7","to":"P6","weight":1},{"from":"P7","to":"P18","weight":1},{"from":"P8","to":"P1","weight":1},{"from":"P8","to":"P25","weight":1},{"from":"P9","to":"P1","weight":1},{"from":"P9","to":"P10","weight":1},{"from":"P9","to":"P13","weight":1},{"from":"P9","to":"P12","weight":1},{"from":"P10","to":"P9","weight":1},{"from":"P10","to":"P28","weight":1},{"from":"P11","to":"P1","weight":1},{"from":"P11","to":"P12","weight":1},{"from":"P11","to":"P39","weight":1},{"from":"P12","to":"P1","weight":1},{"from":"P12","to":"P13","weight":1},{"from":"P13","to":"P1","weight":1},{"from":"P13","to":"P12","weight":1},{"from":"P14","to":"P1","weight":1},{"from":"P14","to":"P15","weight":1},{"from":"P14","to":"P16","weight":1},{"from":"P14","to":"P17","weight":1},{"from":"P14","to":"P18","weight":1},{"from":"P15","to":"P14","weight":1},{"from":"P15","to":"P16","weight":1},{"from":"P15","to":"P9","weight":1},{"from":"P16","to":"P14","weight":1},{"from":"P16","to":"P15","weight":1},{"from":"P16","to":"P38","weight":2},{"from":"P16","to":"P2","weight":1},{"from":"P17","to":"P14","weight":1},{"from":"P17","to":"P4","weight":1},{"from":"P17","to":"P3","weight":1},{"from":"P18","to":"P14","weight":1},{"from":"P18","to":"P7","weight":3},{"from":"P19","to":"P14","weight":1},{"from":"P19","to":"P16","weight":1},{"from":"P20","to":"P3","weight":2},{"from":"P20","to":"P9","weight":3},{"from":"P21","to":"P9","weight":1},{"from":"P21","to":"P16","weight":1},{"from":"P22","to":"P3","weight":1},{"from":"P22","to":"P9","weight":2},{"from":"P22","to":"P4","weight":1},{"from":"P23","to":"P9","weight":2},{"from":"P23","to":"P31","weight":1},{"from":"P24","to":"P1","weight":1},{"from":"P24","to":"P12","weight":1},{"from":"P25","to":"P26","weight":1},{"from":"P25","to":"P27","weight":1},{"from":"P25","to":"P28","weight":1},{"from":"P25","to":"P37","weight":1},{"from":"P26","to":"P25","weight":1},{"from":"P26","to":"P27","weight":1},{"from":"P27","to":"P25","weight":1},{"from":"P27","to":"P28","weight":2},{"from":"P28","to":"P25","weight":1},{"from":"P28","to":"P27","weight":1},{"from":"P29","to":"P30","weight":2},{"from":"P29","to":"P31","weight":1},{"from":"P29","to":"P33","weight":1},{"from":"P29","to":"P36","weight":1},{"from":"P29","to":"P37","weight":1},{"from":"P30","to":"P29","weight":1},{"from":"P30","to":"P31","weight":2},{"from":"P30","to":"P38","weight":1},{"from":"P31","to":"P29","weight":1},{"from":"P31","to":"P32","weight":2},{"from":"P31","to":"P36","weight":1},{"from":"P32","to":"P31","weight":1},{"from":"P32","to":"P33","weight":1},{"from":"P33","to":"P29","weight":1},{"from":"P33","to":"P34","weight":2},{"from":"P33","to":"P35","weight":2},{"from":"P34","to":"P33","weight":1},{"from":"P34","to":"P35","weight":1},{"from":"P35","to":"P33","weight":1},{"from":"P35","to":"P37","weight":1},{"from":"P36","to":"P29","weight":1},{"from":"P36","to":"P32","weight":1},{"from":"P37","to":"P29","weight":1},{"from":"P37","to":"P30","weight":1},{"from":"P38","to":"P30","weight":1},{"from":"P38","to":"P32","weight":1},{"from":"P39","to":"P40","weight":2},{"from":"P40","to":"P39","weight":1}],"details":{"vertices":40,"edges":114,"directed":true,"weighted":true,"acyclic":false,"weightMin":1,"weightMax":3,"negativeWeights":false,"density":0.07307692307692308,"inDegree":{"min":0,"avg":2.85,"max":11},"outDegree":{"min":1,"avg":2.85,"max":10},"selfLoops":0,"components":1}},"problem":"Which groups of pages can a visitor move around freely, getting from any page of a group to any other by following links?","params":{},"result":{"kind":"groups","groups":[["P29","P30","P31","P32","P33","P34","P35","P36","P37","P38"],["P25","P26","P27","P28"],["P39","P40"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"],["P19"],["P20"],["P21"],["P22"],["P23"],["P24"]]},"answer":"The graph has 10 strongly connected components. The ones with more than one vertex are P29, P30, P31, P32, P33, P34, P35, P36, P37 and P38; P25, P26, P27 and P28; P39 and P40; P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 8 more. The other 6 components have one vertex each: P19, P20, P21, P22, P23 and P24.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"current","label":"On the search path","color":"#56B4E9","shape":"ring"},{"id":"waiting","label":"Finished, still on S","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"In a component","color":"#009E73","shape":"filled"},{"id":"component-1","label":"Component 1, 10 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Component 2, 4 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-3","label":"Component 3, 2 vertices","color":"#E69F00","shape":"filled"},{"id":"component-4","label":"Component 4, 18 vertices","color":"#F0E442","shape":"dashed-square"},{"id":"single","label":"A component of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Used to reach a vertex","color":"#009E73","shape":"thick"},{"id":"examined","label":"Leads to a vertex on S","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"s","title":"S, reached and not placed, top first","kind":"list"},{"id":"p","title":"P, possible roots, top first","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"Gabow's path-based algorithm searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and numbers the vertices in the order it reaches them. Stack S holds every vertex reached but not yet placed in a component. Stack P holds the vertices on the search path that can still be the root of a component. An edge to a vertex still on S closes a cycle, so P loses every vertex numbered above that vertex. When a vertex finishes on top of P, it is the root of a component: it and the vertices above it on S form one strongly connected component."},{"say":"Start at P1, the first vertex. P1 gets number 0 and goes on S and P.","ops":[{"v":"P1","state":"current"},{"panel":"s","list":[{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P1","note":"0"}]}]},{"say":"Follow P1 to P2. P2 gets number 1 and goes on S and P.","ops":[{"e":["P1","P2"],"state":"tree"},{"v":"P2","state":"current"},{"panel":"s","list":[{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P2","note":"1"},{"key":"P1","note":"0"}]}]},{"say":"P2 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P2 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P2","P1"],"state":"examined"}]},{"say":"Follow P2 to P3. P3 gets number 2 and goes on S and P.","ops":[{"e":["P2","P3"],"state":"tree"},{"v":"P3","state":"current"},{"panel":"s","list":[{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P3","note":"2"},{"key":"P1","note":"0"}]}]},{"say":"P3 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P3 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P3","P1"],"state":"examined"}]},{"say":"Follow P3 to P9. P9 gets number 3 and goes on S and P.","ops":[{"e":["P3","P9"],"state":"tree"},{"v":"P9","state":"current"},{"panel":"s","list":[{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P9","note":"3"},{"key":"P1","note":"0"}]}]},{"say":"P9 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P9 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P9","P1"],"state":"examined"}]},{"say":"Follow P9 to P10. P10 gets number 4 and goes on S and P.","ops":[{"e":["P9","P10"],"state":"tree"},{"v":"P10","state":"current"},{"panel":"s","list":[{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P10","note":"4"},{"key":"P1","note":"0"}]}]},{"say":"P10 has an edge to P9, which is still on S with number 3. That closes a cycle through P9, so every vertex on P numbered above 3 is in the same component as P9 and can't be its root. Pop P10 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P10","P9"],"state":"examined"}]},{"say":"Follow P10 to P28. P28 gets number 5 and goes on S and P.","ops":[{"e":["P10","P28"],"state":"tree"},{"v":"P28","state":"current"},{"panel":"s","list":[{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"Follow P28 to P25. P25 gets number 6 and goes on S and P.","ops":[{"e":["P28","P25"],"state":"tree"},{"v":"P25","state":"current"},{"panel":"s","list":[{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"Follow P25 to P26. P26 gets number 7 and goes on S and P.","ops":[{"e":["P25","P26"],"state":"tree"},{"v":"P26","state":"current"},{"panel":"s","list":[{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P26 has an edge to P25, which is still on S with number 6. That closes a cycle through P25, so every vertex on P numbered above 6 is in the same component as P25 and can't be its root. Pop P26 off P.","ops":[{"panel":"p","list":[{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P26","P25"],"state":"examined"}]},{"say":"Follow P26 to P27. P27 gets number 8 and goes on S and P.","ops":[{"e":["P26","P27"],"state":"tree"},{"v":"P27","state":"current"},{"panel":"s","list":[{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P27","note":"8"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P27 has an edge to P25, which is still on S with number 6. That closes a cycle through P25, so every vertex on P numbered above 6 is in the same component as P25 and can't be its root. Pop P27 off P.","ops":[{"panel":"p","list":[{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P27","P25"],"state":"examined"}]},{"say":"P27 has an edge to P28, which is still on S with number 5. That closes a cycle through P28, so every vertex on P numbered above 5 is in the same component as P28 and can't be its root. Pop P25 off P.","ops":[{"panel":"p","list":[{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P27","P28"],"state":"examined"}]},{"say":"P27 has no edges left to check. The top of P is P28, so P27 is not a root and stays on S. Back to P26.","ops":[{"v":"P27","state":"waiting"}]},{"say":"P26 has no edges left to check. The top of P is P28, so P26 is not a root and stays on S. Back to P25.","ops":[{"v":"P26","state":"waiting"}]},{"say":"P25 has an edge to P27, which is still on S with number 8. Every vertex on P has a number of 8 or lower, so P stays as it is.","ops":[{"e":["P25","P27"],"state":"examined"}]},{"say":"P25 has an edge to P28, which is still on S with number 5. Every vertex on P has a number of 5 or lower, so P stays as it is.","ops":[{"e":["P25","P28"],"state":"examined"}]},{"say":"Follow P25 to P37. P37 gets number 9 and goes on S and P.","ops":[{"e":["P25","P37"],"state":"tree"},{"v":"P37","state":"current"},{"panel":"s","list":[{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"Follow P37 to P29. P29 gets number 10 and goes on S and P.","ops":[{"e":["P37","P29"],"state":"tree"},{"v":"P29","state":"current"},{"panel":"s","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"Follow P29 to P30. P30 gets number 11 and goes on S and P.","ops":[{"e":["P29","P30"],"state":"tree"},{"v":"P30","state":"current"},{"panel":"s","list":[{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P30 has an edge to P29, which is still on S with number 10. That closes a cycle through P29, so every vertex on P numbered above 10 is in the same component as P29 and can't be its root. Pop P30 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P30","P29"],"state":"examined"}]},{"say":"Follow P30 to P31. P31 gets number 12 and goes on S and P.","ops":[{"e":["P30","P31"],"state":"tree"},{"v":"P31","state":"current"},{"panel":"s","list":[{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P31","note":"12"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P31 has an edge to P29, which is still on S with number 10. That closes a cycle through P29, so every vertex on P numbered above 10 is in the same component as P29 and can't be its root. Pop P31 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P31","P29"],"state":"examined"}]},{"say":"Follow P31 to P32. P32 gets number 13 and goes on S and P.","ops":[{"e":["P31","P32"],"state":"tree"},{"v":"P32","state":"current"},{"panel":"s","list":[{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P32","note":"13"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P32 has an edge to P31, which is still on S with number 12. That closes a cycle through P31, so every vertex on P numbered above 12 is in the same component as P31 and can't be its root. Pop P32 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P32","P31"],"state":"examined"}]},{"say":"Follow P32 to P33. P33 gets number 14 and goes on S and P.","ops":[{"e":["P32","P33"],"state":"tree"},{"v":"P33","state":"current"},{"panel":"s","list":[{"key":"P33","note":"14"},{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P33","note":"14"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P33 has an edge to P29, which is still on S with number 10. That closes a cycle through P29, so every vertex on P numbered above 10 is in the same component as P29 and can't be its root. Pop P33 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P33","P29"],"state":"examined"}]},{"say":"Follow P33 to P34. P34 gets number 15 and goes on S and P.","ops":[{"e":["P33","P34"],"state":"tree"},{"v":"P34","state":"current"},{"panel":"s","list":[{"key":"P34","note":"15"},{"key":"P33","note":"14"},{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P34","note":"15"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P34 has an edge to P33, which is still on S with number 14. That closes a cycle through P33, so every vertex on P numbered above 14 is in the same component as P33 and can't be its root. Pop P34 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P34","P33"],"state":"examined"}]},{"say":"Follow P34 to P35. P35 gets number 16 and goes on S and P.","ops":[{"e":["P34","P35"],"state":"tree"},{"v":"P35","state":"current"},{"panel":"s","list":[{"key":"P35","note":"16"},{"key":"P34","note":"15"},{"key":"P33","note":"14"},{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P35","note":"16"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P35 has an edge to P33, which is still on S with number 14. That closes a cycle through P33, so every vertex on P numbered above 14 is in the same component as P33 and can't be its root. Pop P35 off P.","ops":[{"panel":"p","list":[{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P35","P33"],"state":"examined"}]},{"say":"P35 has an edge to P37, which is still on S with number 9. That closes a cycle through P37, so every vertex on P numbered above 9 is in the same component as P37 and can't be its root. Pop P29 off P.","ops":[{"panel":"p","list":[{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P35","P37"],"state":"examined"}]},{"say":"P35 has no edges left to check. The top of P is P37, so P35 is not a root and stays on S. Back to P34.","ops":[{"v":"P35","state":"waiting"}]},{"say":"P34 has no edges left to check. The top of P is P37, so P34 is not a root and stays on S. Back to P33.","ops":[{"v":"P34","state":"waiting"}]},{"say":"P33 has an edge to P35, which is still on S with number 16. Every vertex on P has a number of 16 or lower, so P stays as it is.","ops":[{"e":["P33","P35"],"state":"examined"}]},{"say":"P33 has no edges left to check. The top of P is P37, so P33 is not a root and stays on S. Back to P32.","ops":[{"v":"P33","state":"waiting"}]},{"say":"P32 has no edges left to check. The top of P is P37, so P32 is not a root and stays on S. Back to P31.","ops":[{"v":"P32","state":"waiting"}]},{"say":"Follow P31 to P36. P36 gets number 17 and goes on S and P.","ops":[{"e":["P31","P36"],"state":"tree"},{"v":"P36","state":"current"},{"panel":"s","list":[{"key":"P36","note":"17"},{"key":"P35","note":"16"},{"key":"P34","note":"15"},{"key":"P33","note":"14"},{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P36","note":"17"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P36 has an edge to P29, which is still on S with number 10. That closes a cycle through P29, so every vertex on P numbered above 10 is in the same component as P29 and can't be its root. Pop P36 off P.","ops":[{"panel":"p","list":[{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P36","P29"],"state":"examined"}]},{"say":"P36 has an edge to P32, which is still on S with number 13. Every vertex on P has a number of 13 or lower, so P stays as it is.","ops":[{"e":["P36","P32"],"state":"examined"}]},{"say":"P36 has no edges left to check. The top of P is P37, so P36 is not a root and stays on S. Back to P31.","ops":[{"v":"P36","state":"waiting"}]},{"say":"P31 has no edges left to check. The top of P is P37, so P31 is not a root and stays on S. Back to P30.","ops":[{"v":"P31","state":"waiting"}]},{"say":"Follow P30 to P38. P38 gets number 18 and goes on S and P.","ops":[{"e":["P30","P38"],"state":"tree"},{"v":"P38","state":"current"},{"panel":"s","list":[{"key":"P38","note":"18"},{"key":"P36","note":"17"},{"key":"P35","note":"16"},{"key":"P34","note":"15"},{"key":"P33","note":"14"},{"key":"P32","note":"13"},{"key":"P31","note":"12"},{"key":"P30","note":"11"},{"key":"P29","note":"10"},{"key":"P37","note":"9"},{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P38","note":"18"},{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]}]},{"say":"P38 has an edge to P30, which is still on S with number 11. That closes a cycle through P30, so every vertex on P numbered above 11 is in the same component as P30 and can't be its root. Pop P38 off P.","ops":[{"panel":"p","list":[{"key":"P37","note":"9"},{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"e":["P38","P30"],"state":"examined"}]},{"say":"P38 has an edge to P32, which is still on S with number 13. Every vertex on P has a number of 13 or lower, so P stays as it is.","ops":[{"e":["P38","P32"],"state":"examined"}]},{"say":"P38 has no edges left to check. The top of P is P37, so P38 is not a root and stays on S. Back to P30.","ops":[{"v":"P38","state":"waiting"}]},{"say":"P30 has no edges left to check. The top of P is P37, so P30 is not a root and stays on S. Back to P29.","ops":[{"v":"P30","state":"waiting"}]},{"say":"P29 has an edge to P31, which is still on S with number 12. Every vertex on P has a number of 12 or lower, so P stays as it is.","ops":[{"e":["P29","P31"],"state":"examined"}]},{"say":"P29 has an edge to P33, which is still on S with number 14. Every vertex on P has a number of 14 or lower, so P stays as it is.","ops":[{"e":["P29","P33"],"state":"examined"}]},{"say":"P29 has an edge to P36, which is still on S with number 17. Every vertex on P has a number of 17 or lower, so P stays as it is.","ops":[{"e":["P29","P36"],"state":"examined"}]},{"say":"P29 has an edge to P37, which is still on S with number 9. Every vertex on P has a number of 9 or lower, so P stays as it is.","ops":[{"e":["P29","P37"],"state":"examined"}]},{"say":"P29 has no edges left to check. The top of P is P37, so P29 is not a root and stays on S. Back to P37.","ops":[{"v":"P29","state":"waiting"}]},{"say":"P37 has an edge to P30, which is still on S with number 11. Every vertex on P has a number of 11 or lower, so P stays as it is.","ops":[{"e":["P37","P30"],"state":"examined"}]},{"say":"P37 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to P37. P38, P36, P35, P34, P33, P32, P31, P30, P29 and P37 form component 1. Back to P25.","ops":[{"panel":"s","list":[{"key":"P27","note":"8"},{"key":"P26","note":"7"},{"key":"P25","note":"6"},{"key":"P28","note":"5"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P28","note":"5"},{"key":"P1","note":"0"}]},{"v":"P38","state":"done"},{"v":"P36","state":"done"},{"v":"P35","state":"done"},{"v":"P34","state":"done"},{"v":"P33","state":"done"},{"v":"P32","state":"done"},{"v":"P31","state":"done"},{"v":"P30","state":"done"},{"v":"P29","state":"done"},{"v":"P37","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"]]}]},{"say":"P25 has no edges left to check. The top of P is P28, so P25 is not a root and stays on S. Back to P28.","ops":[{"v":"P25","state":"waiting"}]},{"say":"P28 has an edge to P27, which is still on S with number 8. Every vertex on P has a number of 8 or lower, so P stays as it is.","ops":[{"e":["P28","P27"],"state":"examined"}]},{"say":"P28 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to P28. P27, P26, P25 and P28 form component 2. Back to P10.","ops":[{"panel":"s","list":[{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P1","note":"0"}]},{"v":"P27","state":"done"},{"v":"P26","state":"done"},{"v":"P25","state":"done"},{"v":"P28","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"]]}]},{"say":"P10 has no edges left to check. The top of P is P1, so P10 is not a root and stays on S. Back to P9.","ops":[{"v":"P10","state":"waiting"}]},{"say":"Follow P9 to P13. P13 gets number 19 and goes on S and P.","ops":[{"e":["P9","P13"],"state":"tree"},{"v":"P13","state":"current"},{"panel":"s","list":[{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P13","note":"19"},{"key":"P1","note":"0"}]}]},{"say":"P13 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P13 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P13","P1"],"state":"examined"}]},{"say":"Follow P13 to P12. P12 gets number 20 and goes on S and P.","ops":[{"e":["P13","P12"],"state":"tree"},{"v":"P12","state":"current"},{"panel":"s","list":[{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P12","note":"20"},{"key":"P1","note":"0"}]}]},{"say":"P12 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P12 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P12","P1"],"state":"examined"}]},{"say":"P12 has an edge to P13, which is still on S with number 19. Every vertex on P has a number of 19 or lower, so P stays as it is.","ops":[{"e":["P12","P13"],"state":"examined"}]},{"say":"P12 has no edges left to check. The top of P is P1, so P12 is not a root and stays on S. Back to P13.","ops":[{"v":"P12","state":"waiting"}]},{"say":"P13 has no edges left to check. The top of P is P1, so P13 is not a root and stays on S. Back to P9.","ops":[{"v":"P13","state":"waiting"}]},{"say":"P9 has an edge to P12, which is still on S with number 20. Every vertex on P has a number of 20 or lower, so P stays as it is.","ops":[{"e":["P9","P12"],"state":"examined"}]},{"say":"P9 has no edges left to check. The top of P is P1, so P9 is not a root and stays on S. Back to P3.","ops":[{"v":"P9","state":"waiting"}]},{"say":"Follow P3 to P8. P8 gets number 21 and goes on S and P.","ops":[{"e":["P3","P8"],"state":"tree"},{"v":"P8","state":"current"},{"panel":"s","list":[{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P8","note":"21"},{"key":"P1","note":"0"}]}]},{"say":"P8 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P8 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P8","P1"],"state":"examined"}]},{"say":"The edge from P8 to P25 leads to a vertex already in a component, so it is skipped. P8 has no edges left to check. The top of P is P1, so P8 is not a root and stays on S. Back to P3.","ops":[{"v":"P8","state":"waiting"}]},{"say":"The edge from P3 to P26 leads to a vertex already in a component, so it is skipped. Follow P3 to P11. P11 gets number 22 and goes on S and P.","ops":[{"e":["P3","P11"],"state":"tree"},{"v":"P11","state":"current"},{"panel":"s","list":[{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P11","note":"22"},{"key":"P1","note":"0"}]}]},{"say":"P11 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P11 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P11","P1"],"state":"examined"}]},{"say":"P11 has an edge to P12, which is still on S with number 20. Every vertex on P has a number of 20 or lower, so P stays as it is.","ops":[{"e":["P11","P12"],"state":"examined"}]},{"say":"Follow P11 to P39. P39 gets number 23 and goes on S and P.","ops":[{"e":["P11","P39"],"state":"tree"},{"v":"P39","state":"current"},{"panel":"s","list":[{"key":"P39","note":"23"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P39","note":"23"},{"key":"P1","note":"0"}]}]},{"say":"Follow P39 to P40. P40 gets number 24 and goes on S and P.","ops":[{"e":["P39","P40"],"state":"tree"},{"v":"P40","state":"current"},{"panel":"s","list":[{"key":"P40","note":"24"},{"key":"P39","note":"23"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P40","note":"24"},{"key":"P39","note":"23"},{"key":"P1","note":"0"}]}]},{"say":"P40 has an edge to P39, which is still on S with number 23. That closes a cycle through P39, so every vertex on P numbered above 23 is in the same component as P39 and can't be its root. Pop P40 off P.","ops":[{"panel":"p","list":[{"key":"P39","note":"23"},{"key":"P1","note":"0"}]},{"e":["P40","P39"],"state":"examined"}]},{"say":"P40 has no edges left to check. The top of P is P39, so P40 is not a root and stays on S. Back to P39.","ops":[{"v":"P40","state":"waiting"}]},{"say":"P39 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to P39. P40 and P39 form component 3. Back to P11.","ops":[{"panel":"s","list":[{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P1","note":"0"}]},{"v":"P40","state":"done"},{"v":"P39","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"]]}]},{"say":"P11 has no edges left to check. The top of P is P1, so P11 is not a root and stays on S. Back to P3.","ops":[{"v":"P11","state":"waiting"}]},{"say":"P3 has no edges left to check. The top of P is P1, so P3 is not a root and stays on S. Back to P2.","ops":[{"v":"P3","state":"waiting"}]},{"say":"Follow P2 to P5. P5 gets number 25 and goes on S and P.","ops":[{"e":["P2","P5"],"state":"tree"},{"v":"P5","state":"current"},{"panel":"s","list":[{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P5","note":"25"},{"key":"P1","note":"0"}]}]},{"say":"P5 has an edge to P2, which is still on S with number 1. That closes a cycle through P2, so every vertex on P numbered above 1 is in the same component as P2 and can't be its root. Pop P5 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P5","P2"],"state":"examined"}]},{"say":"The edge from P5 to P33 leads to a vertex already in a component, so it is skipped. P5 has no edges left to check. The top of P is P1, so P5 is not a root and stays on S. Back to P2.","ops":[{"v":"P5","state":"waiting"}]},{"say":"P2 has an edge to P9, which is still on S with number 3. Every vertex on P has a number of 3 or lower, so P stays as it is.","ops":[{"e":["P2","P9"],"state":"examined"}]},{"say":"The edge from P2 to P29 leads to a vertex already in a component, so it is skipped. P2 has no edges left to check. The top of P is P1, so P2 is not a root and stays on S. Back to P1.","ops":[{"v":"P2","state":"waiting"}]},{"say":"P1 has an edge to P3, which is still on S with number 2. Every vertex on P has a number of 2 or lower, so P stays as it is.","ops":[{"e":["P1","P3"],"state":"examined"}]},{"say":"Follow P1 to P4. P4 gets number 26 and goes on S and P.","ops":[{"e":["P1","P4"],"state":"tree"},{"v":"P4","state":"current"},{"panel":"s","list":[{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P4","note":"26"},{"key":"P1","note":"0"}]}]},{"say":"P4 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P4 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P4","P1"],"state":"examined"}]},{"say":"Follow P4 to P17. P17 gets number 27 and goes on S and P.","ops":[{"e":["P4","P17"],"state":"tree"},{"v":"P17","state":"current"},{"panel":"s","list":[{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P17","note":"27"},{"key":"P1","note":"0"}]}]},{"say":"Follow P17 to P14. P14 gets number 28 and goes on S and P.","ops":[{"e":["P17","P14"],"state":"tree"},{"v":"P14","state":"current"},{"panel":"s","list":[{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P1","note":"0"}]}]},{"say":"P14 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P14 and P17 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P14","P1"],"state":"examined"}]},{"say":"Follow P14 to P15. P15 gets number 29 and goes on S and P.","ops":[{"e":["P14","P15"],"state":"tree"},{"v":"P15","state":"current"},{"panel":"s","list":[{"key":"P15","note":"29"},{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P15","note":"29"},{"key":"P1","note":"0"}]}]},{"say":"P15 has an edge to P14, which is still on S with number 28. That closes a cycle through P14, so every vertex on P numbered above 28 is in the same component as P14 and can't be its root. Pop P15 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P15","P14"],"state":"examined"}]},{"say":"Follow P15 to P16. P16 gets number 30 and goes on S and P.","ops":[{"e":["P15","P16"],"state":"tree"},{"v":"P16","state":"current"},{"panel":"s","list":[{"key":"P16","note":"30"},{"key":"P15","note":"29"},{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P16","note":"30"},{"key":"P1","note":"0"}]}]},{"say":"P16 has an edge to P14, which is still on S with number 28. That closes a cycle through P14, so every vertex on P numbered above 28 is in the same component as P14 and can't be its root. Pop P16 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P16","P14"],"state":"examined"}]},{"say":"P16 has an edge to P15, which is still on S with number 29. Every vertex on P has a number of 29 or lower, so P stays as it is.","ops":[{"e":["P16","P15"],"state":"examined"}]},{"say":"The edge from P16 to P38 leads to a vertex already in a component, so it is skipped. P16 has an edge to P2, which is still on S with number 1. Every vertex on P has a number of 1 or lower, so P stays as it is.","ops":[{"e":["P16","P2"],"state":"examined"}]},{"say":"P16 has no edges left to check. The top of P is P1, so P16 is not a root and stays on S. Back to P15.","ops":[{"v":"P16","state":"waiting"}]},{"say":"P15 has an edge to P9, which is still on S with number 3. Every vertex on P has a number of 3 or lower, so P stays as it is.","ops":[{"e":["P15","P9"],"state":"examined"}]},{"say":"P15 has no edges left to check. The top of P is P1, so P15 is not a root and stays on S. Back to P14.","ops":[{"v":"P15","state":"waiting"}]},{"say":"P14 has an edge to P16, which is still on S with number 30. Every vertex on P has a number of 30 or lower, so P stays as it is.","ops":[{"e":["P14","P16"],"state":"examined"}]},{"say":"P14 has an edge to P17, which is still on S with number 27. Every vertex on P has a number of 27 or lower, so P stays as it is.","ops":[{"e":["P14","P17"],"state":"examined"}]},{"say":"Follow P14 to P18. P18 gets number 31 and goes on S and P.","ops":[{"e":["P14","P18"],"state":"tree"},{"v":"P18","state":"current"},{"panel":"s","list":[{"key":"P18","note":"31"},{"key":"P16","note":"30"},{"key":"P15","note":"29"},{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P18","note":"31"},{"key":"P1","note":"0"}]}]},{"say":"P18 has an edge to P14, which is still on S with number 28. That closes a cycle through P14, so every vertex on P numbered above 28 is in the same component as P14 and can't be its root. Pop P18 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P18","P14"],"state":"examined"}]},{"say":"Follow P18 to P7. P7 gets number 32 and goes on S and P.","ops":[{"e":["P18","P7"],"state":"tree"},{"v":"P7","state":"current"},{"panel":"s","list":[{"key":"P7","note":"32"},{"key":"P18","note":"31"},{"key":"P16","note":"30"},{"key":"P15","note":"29"},{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P7","note":"32"},{"key":"P1","note":"0"}]}]},{"say":"Follow P7 to P6. P6 gets number 33 and goes on S and P.","ops":[{"e":["P7","P6"],"state":"tree"},{"v":"P6","state":"current"},{"panel":"s","list":[{"key":"P6","note":"33"},{"key":"P7","note":"32"},{"key":"P18","note":"31"},{"key":"P16","note":"30"},{"key":"P15","note":"29"},{"key":"P14","note":"28"},{"key":"P17","note":"27"},{"key":"P4","note":"26"},{"key":"P5","note":"25"},{"key":"P11","note":"22"},{"key":"P8","note":"21"},{"key":"P12","note":"20"},{"key":"P13","note":"19"},{"key":"P10","note":"4"},{"key":"P9","note":"3"},{"key":"P3","note":"2"},{"key":"P2","note":"1"},{"key":"P1","note":"0"}]},{"panel":"p","list":[{"key":"P6","note":"33"},{"key":"P7","note":"32"},{"key":"P1","note":"0"}]}]},{"say":"P6 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P6 and P7 off P.","ops":[{"panel":"p","list":[{"key":"P1","note":"0"}]},{"e":["P6","P1"],"state":"examined"}]},{"say":"P6 has an edge to P7, which is still on S with number 32. Every vertex on P has a number of 32 or lower, so P stays as it is.","ops":[{"e":["P6","P7"],"state":"examined"}]},{"say":"P6 has an edge to P8, which is still on S with number 21. Every vertex on P has a number of 21 or lower, so P stays as it is.","ops":[{"e":["P6","P8"],"state":"examined"}]},{"say":"P6 has an edge to P14, which is still on S with number 28. Every vertex on P has a number of 28 or lower, so P stays as it is.","ops":[{"e":["P6","P14"],"state":"examined"}]},{"say":"P6 has no edges left to check. The top of P is P1, so P6 is not a root and stays on S. Back to P7.","ops":[{"v":"P6","state":"waiting"}]},{"say":"P7 has an edge to P18, which is still on S with number 31. Every vertex on P has a number of 31 or lower, so P stays as it is.","ops":[{"e":["P7","P18"],"state":"examined"}]},{"say":"P7 has no edges left to check. The top of P is P1, so P7 is not a root and stays on S. Back to P18.","ops":[{"v":"P7","state":"waiting"}]},{"say":"P18 has no edges left to check. The top of P is P1, so P18 is not a root and stays on S. Back to P14.","ops":[{"v":"P18","state":"waiting"}]},{"say":"P14 has no edges left to check. The top of P is P1, so P14 is not a root and stays on S. Back to P17.","ops":[{"v":"P14","state":"waiting"}]},{"say":"P17 has an edge to P4, which is still on S with number 26. Every vertex on P has a number of 26 or lower, so P stays as it is.","ops":[{"e":["P17","P4"],"state":"examined"}]},{"say":"P17 has an edge to P3, which is still on S with number 2. Every vertex on P has a number of 2 or lower, so P stays as it is.","ops":[{"e":["P17","P3"],"state":"examined"}]},{"say":"P17 has no edges left to check. The top of P is P1, so P17 is not a root and stays on S. Back to P4.","ops":[{"v":"P17","state":"waiting"}]},{"say":"P4 has an edge to P9, which is still on S with number 3. Every vertex on P has a number of 3 or lower, so P stays as it is.","ops":[{"e":["P4","P9"],"state":"examined"}]},{"say":"P4 has no edges left to check. The top of P is P1, so P4 is not a root and stays on S. Back to P1.","ops":[{"v":"P4","state":"waiting"}]},{"say":"P1 has an edge to P6, which is still on S with number 33. Every vertex on P has a number of 33 or lower, so P stays as it is.","ops":[{"e":["P1","P6"],"state":"examined"}]},{"say":"P1 has an edge to P14, which is still on S with number 28. Every vertex on P has a number of 28 or lower, so P stays as it is.","ops":[{"e":["P1","P14"],"state":"examined"}]},{"say":"The edge from P1 to P29 leads to a vertex already in a component, so it is skipped. P1 has an edge to P9, which is still on S with number 3. Every vertex on P has a number of 3 or lower, so P stays as it is.","ops":[{"e":["P1","P9"],"state":"examined"}]},{"say":"P1 has an edge to P10, which is still on S with number 4. Every vertex on P has a number of 4 or lower, so P stays as it is.","ops":[{"e":["P1","P10"],"state":"examined"}]},{"say":"The edges from P1 to P25 and P39 lead to vertices already in components, so they are skipped. P1 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to P1. P6, P7, P18, P16, P15, P14, P17, P4, P5, P11, P8, P12, P13, P10, P9, P3, P2 and P1 form component 4.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P6","state":"done"},{"v":"P7","state":"done"},{"v":"P18","state":"done"},{"v":"P16","state":"done"},{"v":"P15","state":"done"},{"v":"P14","state":"done"},{"v":"P17","state":"done"},{"v":"P4","state":"done"},{"v":"P5","state":"done"},{"v":"P11","state":"done"},{"v":"P8","state":"done"},{"v":"P12","state":"done"},{"v":"P13","state":"done"},{"v":"P10","state":"done"},{"v":"P9","state":"done"},{"v":"P3","state":"done"},{"v":"P2","state":"done"},{"v":"P1","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P19, the next vertex no search has reached. P19 gets number 34 and goes on S and P.","ops":[{"v":"P19","state":"current"},{"panel":"s","list":[{"key":"P19","note":"34"}]},{"panel":"p","list":[{"key":"P19","note":"34"}]}]},{"say":"The edges from P19 to P14 and P16 lead to vertices already in components, so they are skipped. P19 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P19 is component 5 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P19","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P20, the next vertex no search has reached. P20 gets number 35 and goes on S and P.","ops":[{"v":"P20","state":"current"},{"panel":"s","list":[{"key":"P20","note":"35"}]},{"panel":"p","list":[{"key":"P20","note":"35"}]}]},{"say":"The edges from P20 to P3 and P9 lead to vertices already in components, so they are skipped. P20 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P20 is component 6 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P20","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"],["P20"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P21, the next vertex no search has reached. P21 gets number 36 and goes on S and P.","ops":[{"v":"P21","state":"current"},{"panel":"s","list":[{"key":"P21","note":"36"}]},{"panel":"p","list":[{"key":"P21","note":"36"}]}]},{"say":"The edges from P21 to P9 and P16 lead to vertices already in components, so they are skipped. P21 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P21 is component 7 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P21","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"],["P20"],["P21"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P22, the next vertex no search has reached. P22 gets number 37 and goes on S and P.","ops":[{"v":"P22","state":"current"},{"panel":"s","list":[{"key":"P22","note":"37"}]},{"panel":"p","list":[{"key":"P22","note":"37"}]}]},{"say":"The edges from P22 to P3, P9 and P4 lead to vertices already in components, so they are skipped. P22 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P22 is component 8 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P22","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"],["P20"],["P21"],["P22"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P23, the next vertex no search has reached. P23 gets number 38 and goes on S and P.","ops":[{"v":"P23","state":"current"},{"panel":"s","list":[{"key":"P23","note":"38"}]},{"panel":"p","list":[{"key":"P23","note":"38"}]}]},{"say":"The edges from P23 to P9 and P31 lead to vertices already in components, so they are skipped. P23 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P23 is component 9 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P23","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"],["P20"],["P21"],["P22"],["P23"]]}]},{"say":"Every vertex reached so far is in a component. Start a new search at P24, the next vertex no search has reached. P24 gets number 39 and goes on S and P.","ops":[{"v":"P24","state":"current"},{"panel":"s","list":[{"key":"P24","note":"39"}]},{"panel":"p","list":[{"key":"P24","note":"39"}]}]},{"say":"The edges from P24 to P1 and P12 lead to vertices already in components, so they are skipped. P24 has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. P24 is component 10 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"P24","state":"done"},{"panel":"components","groups":[["P38","P36","P35","P34","P33","P32","P31","P30","P29","P37"],["P27","P26","P25","P28"],["P40","P39"],["P6","P7","P18","P16","P15","P14","P17","P4","P5","P11","P8","P12","P13","P10","P9","P3","P2","P1"],["P19"],["P20"],["P21"],["P22"],["P23"],["P24"]]}]},{"say":"Done. Gabow found 10 strongly connected components, 6 of them with one vertex. Each component is listed after every component it has an edge into. Every vertex now shows the component it belongs to.","ops":[{"v":"P38","state":"component-1"},{"v":"P36","state":"component-1"},{"v":"P35","state":"component-1"},{"v":"P34","state":"component-1"},{"v":"P33","state":"component-1"},{"v":"P32","state":"component-1"},{"v":"P31","state":"component-1"},{"v":"P30","state":"component-1"},{"v":"P29","state":"component-1"},{"v":"P37","state":"component-1"},{"v":"P27","state":"component-2"},{"v":"P26","state":"component-2"},{"v":"P25","state":"component-2"},{"v":"P28","state":"component-2"},{"v":"P40","state":"component-3"},{"v":"P39","state":"component-3"},{"v":"P6","state":"component-4"},{"v":"P7","state":"component-4"},{"v":"P18","state":"component-4"},{"v":"P16","state":"component-4"},{"v":"P15","state":"component-4"},{"v":"P14","state":"component-4"},{"v":"P17","state":"component-4"},{"v":"P4","state":"component-4"},{"v":"P5","state":"component-4"},{"v":"P11","state":"component-4"},{"v":"P8","state":"component-4"},{"v":"P12","state":"component-4"},{"v":"P13","state":"component-4"},{"v":"P10","state":"component-4"},{"v":"P9","state":"component-4"},{"v":"P3","state":"component-4"},{"v":"P2","state":"component-4"},{"v":"P1","state":"component-4"},{"v":"P19","state":"single"},{"v":"P20","state":"single"},{"v":"P21","state":"single"},{"v":"P22","state":"single"},{"v":"P23","state":"single"},{"v":"P24","state":"single"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"for _, component := range connectivity.Gabow(g) {\n\tvar names []string\n\tfor _, v := range component {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(strings.Join(names, \", \"))\n}"}
