{"algorithm":"tarjan","about":["A strongly connected component is a group of vertices in a directed graph where each one can reach every other. Tarjan's algorithm finds them all in one depth-first search. It numbers the vertices in the order it reaches them and keeps them on a stack. Each vertex also tracks its lowlink, the smallest number it can reach through the vertices below it in the search and one more edge to a vertex still on the stack.","When the search finishes a vertex whose lowlink is still its own number, nothing it leads to can reach back to an earlier vertex on the stack. That vertex and every vertex above it on the stack form one component, and they leave the stack together. So a component comes out before any component that can reach it.","gograph keeps the search path in a slice instead of recursing, so a long chain doesn't grow the goroutine stack. It costs O(V+E). Use it to find services that call each other in a loop, modules that require each other, or the states of a machine that can all reach each other."],"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 the stack","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 the stack","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"index","title":"Index / lowlink","kind":"table"},{"id":"stack","title":"Stack, top first","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"Tarjan searches depth-first from each vertex no earlier search has reached, in the graph's vertex order. It gives each vertex an index, the order the search reached it in, and a lowlink, the lowest index the vertex is known to reach among the vertices still on the stack. Every vertex goes on the stack when the search reaches it. When a vertex finishes with a lowlink equal to its own index, it is the root of a component: it and the vertices above it on the stack form one strongly connected component."},{"say":"Start at P1, the first vertex. P1 gets index 0 and lowlink 0 and goes on the stack.","ops":[{"v":"P1","state":"current"},{"panel":"stack","list":[{"key":"P1"}]},{"panel":"index","set":{"P1":"0 / 0"}}]},{"say":"Follow P1 to P2. P2 gets index 1 and lowlink 1 and goes on the stack.","ops":[{"e":["P1","P2"],"state":"tree"},{"v":"P2","state":"current"},{"panel":"stack","list":[{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P2":"1 / 1"}}]},{"say":"P2 has an edge to P1, which is still on the stack with index 0. The lowlink of P2 drops from 1 to 0.","ops":[{"panel":"index","set":{"P2":"1 / 0"}},{"e":["P2","P1"],"state":"examined"}]},{"say":"Follow P2 to P3. P3 gets index 2 and lowlink 2 and goes on the stack.","ops":[{"e":["P2","P3"],"state":"tree"},{"v":"P3","state":"current"},{"panel":"stack","list":[{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P3":"2 / 2"}}]},{"say":"P3 has an edge to P1, which is still on the stack with index 0. The lowlink of P3 drops from 2 to 0.","ops":[{"panel":"index","set":{"P3":"2 / 0"}},{"e":["P3","P1"],"state":"examined"}]},{"say":"Follow P3 to P9. P9 gets index 3 and lowlink 3 and goes on the stack.","ops":[{"e":["P3","P9"],"state":"tree"},{"v":"P9","state":"current"},{"panel":"stack","list":[{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P9":"3 / 3"}}]},{"say":"P9 has an edge to P1, which is still on the stack with index 0. The lowlink of P9 drops from 3 to 0.","ops":[{"panel":"index","set":{"P9":"3 / 0"}},{"e":["P9","P1"],"state":"examined"}]},{"say":"Follow P9 to P10. P10 gets index 4 and lowlink 4 and goes on the stack.","ops":[{"e":["P9","P10"],"state":"tree"},{"v":"P10","state":"current"},{"panel":"stack","list":[{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P10":"4 / 4"}}]},{"say":"P10 has an edge to P9, which is still on the stack with index 3. The lowlink of P10 drops from 4 to 3.","ops":[{"panel":"index","set":{"P10":"4 / 3"}},{"e":["P10","P9"],"state":"examined"}]},{"say":"Follow P10 to P28. P28 gets index 5 and lowlink 5 and goes on the stack.","ops":[{"e":["P10","P28"],"state":"tree"},{"v":"P28","state":"current"},{"panel":"stack","list":[{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P28":"5 / 5"}}]},{"say":"Follow P28 to P25. P25 gets index 6 and lowlink 6 and goes on the stack.","ops":[{"e":["P28","P25"],"state":"tree"},{"v":"P25","state":"current"},{"panel":"stack","list":[{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P25":"6 / 6"}}]},{"say":"Follow P25 to P26. P26 gets index 7 and lowlink 7 and goes on the stack.","ops":[{"e":["P25","P26"],"state":"tree"},{"v":"P26","state":"current"},{"panel":"stack","list":[{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P26":"7 / 7"}}]},{"say":"P26 has an edge to P25, which is still on the stack with index 6. The lowlink of P26 drops from 7 to 6.","ops":[{"panel":"index","set":{"P26":"7 / 6"}},{"e":["P26","P25"],"state":"examined"}]},{"say":"Follow P26 to P27. P27 gets index 8 and lowlink 8 and goes on the stack.","ops":[{"e":["P26","P27"],"state":"tree"},{"v":"P27","state":"current"},{"panel":"stack","list":[{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P27":"8 / 8"}}]},{"say":"P27 has an edge to P25, which is still on the stack with index 6. The lowlink of P27 drops from 8 to 6.","ops":[{"panel":"index","set":{"P27":"8 / 6"}},{"e":["P27","P25"],"state":"examined"}]},{"say":"P27 has an edge to P28, which is still on the stack with index 5. The lowlink of P27 drops from 6 to 5.","ops":[{"panel":"index","set":{"P27":"8 / 5"}},{"e":["P27","P28"],"state":"examined"}]},{"say":"P27 has no edges left to check. Its lowlink, 5, is lower than its index, 8, so it stays on the stack until the root of its component finishes. Back to P26, whose lowlink drops from 6 to 5.","ops":[{"v":"P27","state":"waiting"},{"panel":"index","set":{"P26":"7 / 5"}}]},{"say":"P26 has no edges left to check. Its lowlink, 5, is lower than its index, 7, so it stays on the stack until the root of its component finishes. Back to P25, whose lowlink drops from 6 to 5.","ops":[{"v":"P26","state":"waiting"},{"panel":"index","set":{"P25":"6 / 5"}}]},{"say":"P25 has an edge to P27, which is still on the stack with index 8. The lowlink of P25 stays 5, since that is no higher.","ops":[{"e":["P25","P27"],"state":"examined"}]},{"say":"P25 has an edge to P28, which is still on the stack with index 5. The lowlink of P25 stays 5, since that is no higher.","ops":[{"e":["P25","P28"],"state":"examined"}]},{"say":"Follow P25 to P37. P37 gets index 9 and lowlink 9 and goes on the stack.","ops":[{"e":["P25","P37"],"state":"tree"},{"v":"P37","state":"current"},{"panel":"stack","list":[{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P37":"9 / 9"}}]},{"say":"Follow P37 to P29. P29 gets index 10 and lowlink 10 and goes on the stack.","ops":[{"e":["P37","P29"],"state":"tree"},{"v":"P29","state":"current"},{"panel":"stack","list":[{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P29":"10 / 10"}}]},{"say":"Follow P29 to P30. P30 gets index 11 and lowlink 11 and goes on the stack.","ops":[{"e":["P29","P30"],"state":"tree"},{"v":"P30","state":"current"},{"panel":"stack","list":[{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P30":"11 / 11"}}]},{"say":"P30 has an edge to P29, which is still on the stack with index 10. The lowlink of P30 drops from 11 to 10.","ops":[{"panel":"index","set":{"P30":"11 / 10"}},{"e":["P30","P29"],"state":"examined"}]},{"say":"Follow P30 to P31. P31 gets index 12 and lowlink 12 and goes on the stack.","ops":[{"e":["P30","P31"],"state":"tree"},{"v":"P31","state":"current"},{"panel":"stack","list":[{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P31":"12 / 12"}}]},{"say":"P31 has an edge to P29, which is still on the stack with index 10. The lowlink of P31 drops from 12 to 10.","ops":[{"panel":"index","set":{"P31":"12 / 10"}},{"e":["P31","P29"],"state":"examined"}]},{"say":"Follow P31 to P32. P32 gets index 13 and lowlink 13 and goes on the stack.","ops":[{"e":["P31","P32"],"state":"tree"},{"v":"P32","state":"current"},{"panel":"stack","list":[{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P32":"13 / 13"}}]},{"say":"P32 has an edge to P31, which is still on the stack with index 12. The lowlink of P32 drops from 13 to 12.","ops":[{"panel":"index","set":{"P32":"13 / 12"}},{"e":["P32","P31"],"state":"examined"}]},{"say":"Follow P32 to P33. P33 gets index 14 and lowlink 14 and goes on the stack.","ops":[{"e":["P32","P33"],"state":"tree"},{"v":"P33","state":"current"},{"panel":"stack","list":[{"key":"P33"},{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P33":"14 / 14"}}]},{"say":"P33 has an edge to P29, which is still on the stack with index 10. The lowlink of P33 drops from 14 to 10.","ops":[{"panel":"index","set":{"P33":"14 / 10"}},{"e":["P33","P29"],"state":"examined"}]},{"say":"Follow P33 to P34. P34 gets index 15 and lowlink 15 and goes on the stack.","ops":[{"e":["P33","P34"],"state":"tree"},{"v":"P34","state":"current"},{"panel":"stack","list":[{"key":"P34"},{"key":"P33"},{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P34":"15 / 15"}}]},{"say":"P34 has an edge to P33, which is still on the stack with index 14. The lowlink of P34 drops from 15 to 14.","ops":[{"panel":"index","set":{"P34":"15 / 14"}},{"e":["P34","P33"],"state":"examined"}]},{"say":"Follow P34 to P35. P35 gets index 16 and lowlink 16 and goes on the stack.","ops":[{"e":["P34","P35"],"state":"tree"},{"v":"P35","state":"current"},{"panel":"stack","list":[{"key":"P35"},{"key":"P34"},{"key":"P33"},{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P35":"16 / 16"}}]},{"say":"P35 has an edge to P33, which is still on the stack with index 14. The lowlink of P35 drops from 16 to 14.","ops":[{"panel":"index","set":{"P35":"16 / 14"}},{"e":["P35","P33"],"state":"examined"}]},{"say":"P35 has an edge to P37, which is still on the stack with index 9. The lowlink of P35 drops from 14 to 9.","ops":[{"panel":"index","set":{"P35":"16 / 9"}},{"e":["P35","P37"],"state":"examined"}]},{"say":"P35 has no edges left to check. Its lowlink, 9, is lower than its index, 16, so it stays on the stack until the root of its component finishes. Back to P34, whose lowlink drops from 14 to 9.","ops":[{"v":"P35","state":"waiting"},{"panel":"index","set":{"P34":"15 / 9"}}]},{"say":"P34 has no edges left to check. Its lowlink, 9, is lower than its index, 15, so it stays on the stack until the root of its component finishes. Back to P33, whose lowlink drops from 10 to 9.","ops":[{"v":"P34","state":"waiting"},{"panel":"index","set":{"P33":"14 / 9"}}]},{"say":"P33 has an edge to P35, which is still on the stack with index 16. The lowlink of P33 stays 9, since that is no higher.","ops":[{"e":["P33","P35"],"state":"examined"}]},{"say":"P33 has no edges left to check. Its lowlink, 9, is lower than its index, 14, so it stays on the stack until the root of its component finishes. Back to P32, whose lowlink drops from 12 to 9.","ops":[{"v":"P33","state":"waiting"},{"panel":"index","set":{"P32":"13 / 9"}}]},{"say":"P32 has no edges left to check. Its lowlink, 9, is lower than its index, 13, so it stays on the stack until the root of its component finishes. Back to P31, whose lowlink drops from 10 to 9.","ops":[{"v":"P32","state":"waiting"},{"panel":"index","set":{"P31":"12 / 9"}}]},{"say":"Follow P31 to P36. P36 gets index 17 and lowlink 17 and goes on the stack.","ops":[{"e":["P31","P36"],"state":"tree"},{"v":"P36","state":"current"},{"panel":"stack","list":[{"key":"P36"},{"key":"P35"},{"key":"P34"},{"key":"P33"},{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P36":"17 / 17"}}]},{"say":"P36 has an edge to P29, which is still on the stack with index 10. The lowlink of P36 drops from 17 to 10.","ops":[{"panel":"index","set":{"P36":"17 / 10"}},{"e":["P36","P29"],"state":"examined"}]},{"say":"P36 has an edge to P32, which is still on the stack with index 13. The lowlink of P36 stays 10, since that is no higher.","ops":[{"e":["P36","P32"],"state":"examined"}]},{"say":"P36 has no edges left to check. Its lowlink, 10, is lower than its index, 17, so it stays on the stack until the root of its component finishes. Back to P31, whose lowlink stays 9.","ops":[{"v":"P36","state":"waiting"}]},{"say":"P31 has no edges left to check. Its lowlink, 9, is lower than its index, 12, so it stays on the stack until the root of its component finishes. Back to P30, whose lowlink drops from 10 to 9.","ops":[{"v":"P31","state":"waiting"},{"panel":"index","set":{"P30":"11 / 9"}}]},{"say":"Follow P30 to P38. P38 gets index 18 and lowlink 18 and goes on the stack.","ops":[{"e":["P30","P38"],"state":"tree"},{"v":"P38","state":"current"},{"panel":"stack","list":[{"key":"P38"},{"key":"P36"},{"key":"P35"},{"key":"P34"},{"key":"P33"},{"key":"P32"},{"key":"P31"},{"key":"P30"},{"key":"P29"},{"key":"P37"},{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P38":"18 / 18"}}]},{"say":"P38 has an edge to P30, which is still on the stack with index 11. The lowlink of P38 drops from 18 to 11.","ops":[{"panel":"index","set":{"P38":"18 / 11"}},{"e":["P38","P30"],"state":"examined"}]},{"say":"P38 has an edge to P32, which is still on the stack with index 13. The lowlink of P38 stays 11, since that is no higher.","ops":[{"e":["P38","P32"],"state":"examined"}]},{"say":"P38 has no edges left to check. Its lowlink, 11, is lower than its index, 18, so it stays on the stack until the root of its component finishes. Back to P30, whose lowlink stays 9.","ops":[{"v":"P38","state":"waiting"}]},{"say":"P30 has no edges left to check. Its lowlink, 9, is lower than its index, 11, so it stays on the stack until the root of its component finishes. Back to P29, whose lowlink drops from 10 to 9.","ops":[{"v":"P30","state":"waiting"},{"panel":"index","set":{"P29":"10 / 9"}}]},{"say":"P29 has an edge to P31, which is still on the stack with index 12. The lowlink of P29 stays 9, since that is no higher.","ops":[{"e":["P29","P31"],"state":"examined"}]},{"say":"P29 has an edge to P33, which is still on the stack with index 14. The lowlink of P29 stays 9, since that is no higher.","ops":[{"e":["P29","P33"],"state":"examined"}]},{"say":"P29 has an edge to P36, which is still on the stack with index 17. The lowlink of P29 stays 9, since that is no higher.","ops":[{"e":["P29","P36"],"state":"examined"}]},{"say":"P29 has an edge to P37, which is still on the stack with index 9. The lowlink of P29 stays 9, since that is no higher.","ops":[{"e":["P29","P37"],"state":"examined"}]},{"say":"P29 has no edges left to check. Its lowlink, 9, is lower than its index, 10, so it stays on the stack until the root of its component finishes. Back to P37, whose lowlink stays 9.","ops":[{"v":"P29","state":"waiting"}]},{"say":"P37 has an edge to P30, which is still on the stack with index 11. The lowlink of P37 stays 9, since that is no higher.","ops":[{"e":["P37","P30"],"state":"examined"}]},{"say":"P37 has no edges left to check. Its lowlink equals its index, 9, so it is the root of a component. Pop the stack down to P37. P38, P36, P35, P34, P33, P32, P31, P30, P29 and P37 form component 1. Back to P25.","ops":[{"panel":"stack","list":[{"key":"P27"},{"key":"P26"},{"key":"P25"},{"key":"P28"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"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. Its lowlink, 5, is lower than its index, 6, so it stays on the stack until the root of its component finishes. Back to P28, whose lowlink stays 5.","ops":[{"v":"P25","state":"waiting"}]},{"say":"P28 has an edge to P27, which is still on the stack with index 8. The lowlink of P28 stays 5, since that is no higher.","ops":[{"e":["P28","P27"],"state":"examined"}]},{"say":"P28 has no edges left to check. Its lowlink equals its index, 5, so it is the root of a component. Pop the stack down to P28. P27, P26, P25 and P28 form component 2. Back to P10.","ops":[{"panel":"stack","list":[{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"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. Its lowlink, 3, is lower than its index, 4, so it stays on the stack until the root of its component finishes. Back to P9, whose lowlink stays 0.","ops":[{"v":"P10","state":"waiting"}]},{"say":"Follow P9 to P13. P13 gets index 19 and lowlink 19 and goes on the stack.","ops":[{"e":["P9","P13"],"state":"tree"},{"v":"P13","state":"current"},{"panel":"stack","list":[{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P13":"19 / 19"}}]},{"say":"P13 has an edge to P1, which is still on the stack with index 0. The lowlink of P13 drops from 19 to 0.","ops":[{"panel":"index","set":{"P13":"19 / 0"}},{"e":["P13","P1"],"state":"examined"}]},{"say":"Follow P13 to P12. P12 gets index 20 and lowlink 20 and goes on the stack.","ops":[{"e":["P13","P12"],"state":"tree"},{"v":"P12","state":"current"},{"panel":"stack","list":[{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P12":"20 / 20"}}]},{"say":"P12 has an edge to P1, which is still on the stack with index 0. The lowlink of P12 drops from 20 to 0.","ops":[{"panel":"index","set":{"P12":"20 / 0"}},{"e":["P12","P1"],"state":"examined"}]},{"say":"P12 has an edge to P13, which is still on the stack with index 19. The lowlink of P12 stays 0, since that is no higher.","ops":[{"e":["P12","P13"],"state":"examined"}]},{"say":"P12 has no edges left to check. Its lowlink, 0, is lower than its index, 20, so it stays on the stack until the root of its component finishes. Back to P13, whose lowlink stays 0.","ops":[{"v":"P12","state":"waiting"}]},{"say":"P13 has no edges left to check. Its lowlink, 0, is lower than its index, 19, so it stays on the stack until the root of its component finishes. Back to P9, whose lowlink stays 0.","ops":[{"v":"P13","state":"waiting"}]},{"say":"P9 has an edge to P12, which is still on the stack with index 20. The lowlink of P9 stays 0, since that is no higher.","ops":[{"e":["P9","P12"],"state":"examined"}]},{"say":"P9 has no edges left to check. Its lowlink, 0, is lower than its index, 3, so it stays on the stack until the root of its component finishes. Back to P3, whose lowlink stays 0.","ops":[{"v":"P9","state":"waiting"}]},{"say":"Follow P3 to P8. P8 gets index 21 and lowlink 21 and goes on the stack.","ops":[{"e":["P3","P8"],"state":"tree"},{"v":"P8","state":"current"},{"panel":"stack","list":[{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P8":"21 / 21"}}]},{"say":"P8 has an edge to P1, which is still on the stack with index 0. The lowlink of P8 drops from 21 to 0.","ops":[{"panel":"index","set":{"P8":"21 / 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. Its lowlink, 0, is lower than its index, 21, so it stays on the stack until the root of its component finishes. Back to P3, whose lowlink stays 0.","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 index 22 and lowlink 22 and goes on the stack.","ops":[{"e":["P3","P11"],"state":"tree"},{"v":"P11","state":"current"},{"panel":"stack","list":[{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P11":"22 / 22"}}]},{"say":"P11 has an edge to P1, which is still on the stack with index 0. The lowlink of P11 drops from 22 to 0.","ops":[{"panel":"index","set":{"P11":"22 / 0"}},{"e":["P11","P1"],"state":"examined"}]},{"say":"P11 has an edge to P12, which is still on the stack with index 20. The lowlink of P11 stays 0, since that is no higher.","ops":[{"e":["P11","P12"],"state":"examined"}]},{"say":"Follow P11 to P39. P39 gets index 23 and lowlink 23 and goes on the stack.","ops":[{"e":["P11","P39"],"state":"tree"},{"v":"P39","state":"current"},{"panel":"stack","list":[{"key":"P39"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P39":"23 / 23"}}]},{"say":"Follow P39 to P40. P40 gets index 24 and lowlink 24 and goes on the stack.","ops":[{"e":["P39","P40"],"state":"tree"},{"v":"P40","state":"current"},{"panel":"stack","list":[{"key":"P40"},{"key":"P39"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P40":"24 / 24"}}]},{"say":"P40 has an edge to P39, which is still on the stack with index 23. The lowlink of P40 drops from 24 to 23.","ops":[{"panel":"index","set":{"P40":"24 / 23"}},{"e":["P40","P39"],"state":"examined"}]},{"say":"P40 has no edges left to check. Its lowlink, 23, is lower than its index, 24, so it stays on the stack until the root of its component finishes. Back to P39, whose lowlink stays 23.","ops":[{"v":"P40","state":"waiting"}]},{"say":"P39 has no edges left to check. Its lowlink equals its index, 23, so it is the root of a component. Pop the stack down to P39. P40 and P39 form component 3. Back to P11.","ops":[{"panel":"stack","list":[{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"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. Its lowlink, 0, is lower than its index, 22, so it stays on the stack until the root of its component finishes. Back to P3, whose lowlink stays 0.","ops":[{"v":"P11","state":"waiting"}]},{"say":"P3 has no edges left to check. Its lowlink, 0, is lower than its index, 2, so it stays on the stack until the root of its component finishes. Back to P2, whose lowlink stays 0.","ops":[{"v":"P3","state":"waiting"}]},{"say":"Follow P2 to P5. P5 gets index 25 and lowlink 25 and goes on the stack.","ops":[{"e":["P2","P5"],"state":"tree"},{"v":"P5","state":"current"},{"panel":"stack","list":[{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P5":"25 / 25"}}]},{"say":"P5 has an edge to P2, which is still on the stack with index 1. The lowlink of P5 drops from 25 to 1.","ops":[{"panel":"index","set":{"P5":"25 / 1"}},{"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. Its lowlink, 1, is lower than its index, 25, so it stays on the stack until the root of its component finishes. Back to P2, whose lowlink stays 0.","ops":[{"v":"P5","state":"waiting"}]},{"say":"P2 has an edge to P9, which is still on the stack with index 3. The lowlink of P2 stays 0, since that is no higher.","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. Its lowlink, 0, is lower than its index, 1, so it stays on the stack until the root of its component finishes. Back to P1, whose lowlink stays 0.","ops":[{"v":"P2","state":"waiting"}]},{"say":"P1 has an edge to P3, which is still on the stack with index 2. The lowlink of P1 stays 0, since that is no higher.","ops":[{"e":["P1","P3"],"state":"examined"}]},{"say":"Follow P1 to P4. P4 gets index 26 and lowlink 26 and goes on the stack.","ops":[{"e":["P1","P4"],"state":"tree"},{"v":"P4","state":"current"},{"panel":"stack","list":[{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P4":"26 / 26"}}]},{"say":"P4 has an edge to P1, which is still on the stack with index 0. The lowlink of P4 drops from 26 to 0.","ops":[{"panel":"index","set":{"P4":"26 / 0"}},{"e":["P4","P1"],"state":"examined"}]},{"say":"Follow P4 to P17. P17 gets index 27 and lowlink 27 and goes on the stack.","ops":[{"e":["P4","P17"],"state":"tree"},{"v":"P17","state":"current"},{"panel":"stack","list":[{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P17":"27 / 27"}}]},{"say":"Follow P17 to P14. P14 gets index 28 and lowlink 28 and goes on the stack.","ops":[{"e":["P17","P14"],"state":"tree"},{"v":"P14","state":"current"},{"panel":"stack","list":[{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P14":"28 / 28"}}]},{"say":"P14 has an edge to P1, which is still on the stack with index 0. The lowlink of P14 drops from 28 to 0.","ops":[{"panel":"index","set":{"P14":"28 / 0"}},{"e":["P14","P1"],"state":"examined"}]},{"say":"Follow P14 to P15. P15 gets index 29 and lowlink 29 and goes on the stack.","ops":[{"e":["P14","P15"],"state":"tree"},{"v":"P15","state":"current"},{"panel":"stack","list":[{"key":"P15"},{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P15":"29 / 29"}}]},{"say":"P15 has an edge to P14, which is still on the stack with index 28. The lowlink of P15 drops from 29 to 28.","ops":[{"panel":"index","set":{"P15":"29 / 28"}},{"e":["P15","P14"],"state":"examined"}]},{"say":"Follow P15 to P16. P16 gets index 30 and lowlink 30 and goes on the stack.","ops":[{"e":["P15","P16"],"state":"tree"},{"v":"P16","state":"current"},{"panel":"stack","list":[{"key":"P16"},{"key":"P15"},{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P16":"30 / 30"}}]},{"say":"P16 has an edge to P14, which is still on the stack with index 28. The lowlink of P16 drops from 30 to 28.","ops":[{"panel":"index","set":{"P16":"30 / 28"}},{"e":["P16","P14"],"state":"examined"}]},{"say":"P16 has an edge to P15, which is still on the stack with index 29. The lowlink of P16 stays 28, since that is no higher.","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 the stack with index 1. The lowlink of P16 drops from 28 to 1.","ops":[{"panel":"index","set":{"P16":"30 / 1"}},{"e":["P16","P2"],"state":"examined"}]},{"say":"P16 has no edges left to check. Its lowlink, 1, is lower than its index, 30, so it stays on the stack until the root of its component finishes. Back to P15, whose lowlink drops from 28 to 1.","ops":[{"v":"P16","state":"waiting"},{"panel":"index","set":{"P15":"29 / 1"}}]},{"say":"P15 has an edge to P9, which is still on the stack with index 3. The lowlink of P15 stays 1, since that is no higher.","ops":[{"e":["P15","P9"],"state":"examined"}]},{"say":"P15 has no edges left to check. Its lowlink, 1, is lower than its index, 29, so it stays on the stack until the root of its component finishes. Back to P14, whose lowlink stays 0.","ops":[{"v":"P15","state":"waiting"}]},{"say":"P14 has an edge to P16, which is still on the stack with index 30. The lowlink of P14 stays 0, since that is no higher.","ops":[{"e":["P14","P16"],"state":"examined"}]},{"say":"P14 has an edge to P17, which is still on the stack with index 27. The lowlink of P14 stays 0, since that is no higher.","ops":[{"e":["P14","P17"],"state":"examined"}]},{"say":"Follow P14 to P18. P18 gets index 31 and lowlink 31 and goes on the stack.","ops":[{"e":["P14","P18"],"state":"tree"},{"v":"P18","state":"current"},{"panel":"stack","list":[{"key":"P18"},{"key":"P16"},{"key":"P15"},{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P18":"31 / 31"}}]},{"say":"P18 has an edge to P14, which is still on the stack with index 28. The lowlink of P18 drops from 31 to 28.","ops":[{"panel":"index","set":{"P18":"31 / 28"}},{"e":["P18","P14"],"state":"examined"}]},{"say":"Follow P18 to P7. P7 gets index 32 and lowlink 32 and goes on the stack.","ops":[{"e":["P18","P7"],"state":"tree"},{"v":"P7","state":"current"},{"panel":"stack","list":[{"key":"P7"},{"key":"P18"},{"key":"P16"},{"key":"P15"},{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P7":"32 / 32"}}]},{"say":"Follow P7 to P6. P6 gets index 33 and lowlink 33 and goes on the stack.","ops":[{"e":["P7","P6"],"state":"tree"},{"v":"P6","state":"current"},{"panel":"stack","list":[{"key":"P6"},{"key":"P7"},{"key":"P18"},{"key":"P16"},{"key":"P15"},{"key":"P14"},{"key":"P17"},{"key":"P4"},{"key":"P5"},{"key":"P11"},{"key":"P8"},{"key":"P12"},{"key":"P13"},{"key":"P10"},{"key":"P9"},{"key":"P3"},{"key":"P2"},{"key":"P1"}]},{"panel":"index","set":{"P6":"33 / 33"}}]},{"say":"P6 has an edge to P1, which is still on the stack with index 0. The lowlink of P6 drops from 33 to 0.","ops":[{"panel":"index","set":{"P6":"33 / 0"}},{"e":["P6","P1"],"state":"examined"}]},{"say":"P6 has an edge to P7, which is still on the stack with index 32. The lowlink of P6 stays 0, since that is no higher.","ops":[{"e":["P6","P7"],"state":"examined"}]},{"say":"P6 has an edge to P8, which is still on the stack with index 21. The lowlink of P6 stays 0, since that is no higher.","ops":[{"e":["P6","P8"],"state":"examined"}]},{"say":"P6 has an edge to P14, which is still on the stack with index 28. The lowlink of P6 stays 0, since that is no higher.","ops":[{"e":["P6","P14"],"state":"examined"}]},{"say":"P6 has no edges left to check. Its lowlink, 0, is lower than its index, 33, so it stays on the stack until the root of its component finishes. Back to P7, whose lowlink drops from 32 to 0.","ops":[{"v":"P6","state":"waiting"},{"panel":"index","set":{"P7":"32 / 0"}}]},{"say":"P7 has an edge to P18, which is still on the stack with index 31. The lowlink of P7 stays 0, since that is no higher.","ops":[{"e":["P7","P18"],"state":"examined"}]},{"say":"P7 has no edges left to check. Its lowlink, 0, is lower than its index, 32, so it stays on the stack until the root of its component finishes. Back to P18, whose lowlink drops from 28 to 0.","ops":[{"v":"P7","state":"waiting"},{"panel":"index","set":{"P18":"31 / 0"}}]},{"say":"P18 has no edges left to check. Its lowlink, 0, is lower than its index, 31, so it stays on the stack until the root of its component finishes. Back to P14, whose lowlink stays 0.","ops":[{"v":"P18","state":"waiting"}]},{"say":"P14 has no edges left to check. Its lowlink, 0, is lower than its index, 28, so it stays on the stack until the root of its component finishes. Back to P17, whose lowlink drops from 27 to 0.","ops":[{"v":"P14","state":"waiting"},{"panel":"index","set":{"P17":"27 / 0"}}]},{"say":"P17 has an edge to P4, which is still on the stack with index 26. The lowlink of P17 stays 0, since that is no higher.","ops":[{"e":["P17","P4"],"state":"examined"}]},{"say":"P17 has an edge to P3, which is still on the stack with index 2. The lowlink of P17 stays 0, since that is no higher.","ops":[{"e":["P17","P3"],"state":"examined"}]},{"say":"P17 has no edges left to check. Its lowlink, 0, is lower than its index, 27, so it stays on the stack until the root of its component finishes. Back to P4, whose lowlink stays 0.","ops":[{"v":"P17","state":"waiting"}]},{"say":"P4 has an edge to P9, which is still on the stack with index 3. The lowlink of P4 stays 0, since that is no higher.","ops":[{"e":["P4","P9"],"state":"examined"}]},{"say":"P4 has no edges left to check. Its lowlink, 0, is lower than its index, 26, so it stays on the stack until the root of its component finishes. Back to P1, whose lowlink stays 0.","ops":[{"v":"P4","state":"waiting"}]},{"say":"P1 has an edge to P6, which is still on the stack with index 33. The lowlink of P1 stays 0, since that is no higher.","ops":[{"e":["P1","P6"],"state":"examined"}]},{"say":"P1 has an edge to P14, which is still on the stack with index 28. The lowlink of P1 stays 0, since that is no higher.","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 the stack with index 3. The lowlink of P1 stays 0, since that is no higher.","ops":[{"e":["P1","P9"],"state":"examined"}]},{"say":"P1 has an edge to P10, which is still on the stack with index 4. The lowlink of P1 stays 0, since that is no higher.","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. Its lowlink equals its index, 0, so it is the root of a component. Pop the stack 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":"stack","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 index 34 and lowlink 34 and goes on the stack.","ops":[{"v":"P19","state":"current"},{"panel":"stack","list":[{"key":"P19"}]},{"panel":"index","set":{"P19":"34 / 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. Its lowlink equals its index, 34, so it is the root of a component. Pop it off the stack. P19 is component 5 on its own.","ops":[{"panel":"stack","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 index 35 and lowlink 35 and goes on the stack.","ops":[{"v":"P20","state":"current"},{"panel":"stack","list":[{"key":"P20"}]},{"panel":"index","set":{"P20":"35 / 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. Its lowlink equals its index, 35, so it is the root of a component. Pop it off the stack. P20 is component 6 on its own.","ops":[{"panel":"stack","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 index 36 and lowlink 36 and goes on the stack.","ops":[{"v":"P21","state":"current"},{"panel":"stack","list":[{"key":"P21"}]},{"panel":"index","set":{"P21":"36 / 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. Its lowlink equals its index, 36, so it is the root of a component. Pop it off the stack. P21 is component 7 on its own.","ops":[{"panel":"stack","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 index 37 and lowlink 37 and goes on the stack.","ops":[{"v":"P22","state":"current"},{"panel":"stack","list":[{"key":"P22"}]},{"panel":"index","set":{"P22":"37 / 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. Its lowlink equals its index, 37, so it is the root of a component. Pop it off the stack. P22 is component 8 on its own.","ops":[{"panel":"stack","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 index 38 and lowlink 38 and goes on the stack.","ops":[{"v":"P23","state":"current"},{"panel":"stack","list":[{"key":"P23"}]},{"panel":"index","set":{"P23":"38 / 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. Its lowlink equals its index, 38, so it is the root of a component. Pop it off the stack. P23 is component 9 on its own.","ops":[{"panel":"stack","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 index 39 and lowlink 39 and goes on the stack.","ops":[{"v":"P24","state":"current"},{"panel":"stack","list":[{"key":"P24"}]},{"panel":"index","set":{"P24":"39 / 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. Its lowlink equals its index, 39, so it is the root of a component. Pop it off the stack. P24 is component 10 on its own.","ops":[{"panel":"stack","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. Tarjan 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.Tarjan(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}"}
