20:
221:
is a cut for which the size or weight of the cut is not larger than the size of any other cut. For an unweighted graph, the minimum cut would simply be the cut with the least edges. For a weighted graph, the sum of all edges' weight on the cut determines whether it is a minimum cut. In practice, the
47:
weighted graphs with non-negative weights. It was proposed by
Mechthild Stoer and Frank Wagner in 1995. The essential idea of this algorithm is to shrink the graph by merging the most intensive vertices, until the graph only contains two combined vertex sets. At each phase, the algorithm finds the
1784:
is determined. After one phase of the
MinimumCutPhase, the two vertices are merged as a new vertex, and edges from the two vertices to a remaining vertex are replaced by an edge weighted by the sum of the weights of the previous two edges. Edges joining the merged nodes are removed. If there is a
2126:
in this phase. By merging them into node 1+5, the new graph is as shown in step 2. In this phase, the weight of cut is 5, which is the summation of edges (1,2) and (1,5). Right now, the first loop of
MinimumCut is completed.
2173:
The following steps repeat the same operations on the merged graph, until there is only one edge in the graph, as shown in step 7. The global minimum cut has edge (2,3) and edge (6,7), which is detected in step 5.
3421:
3513:
3313:
1619:
854:
3873:
4130:
3580:
2842:
1192:
2312:
1945:
on a same side. Therefore, the algorithm would merge them as one node. In addition, the
MinimumCut would record and update the global minimum cut after each MinimumCutPhase. After
4603:
4033:
2928:
683:
3635:
2716:
2755:
2683:
2410:
1116:
2971:
2340:
2243:
2208:
1762:
4500:
3005:
1542:
1223:
280:
3707:
3671:
2150:. The next heaviest edges is (2,3) or (1+5,6), we choose (1+5,6) thus node 6 is added to the set. Then we compare edge (2,3) and (6,7) and choose node 3 to put in set
1346:
312:
1386:
1308:
1159:
4248:
1654:
3948:
3079:
3052:
2872:
2624:
2557:
715:
627:
4529:
4451:
4421:
1969:
4391:
2363:
1040:
917:
4368:
4348:
4328:
4308:
4288:
4268:
4213:
4193:
4173:
4153:
3896:
3791:
3771:
3751:
3731:
3199:
3179:
3159:
3139:
3119:
3099:
3025:
2775:
2644:
2597:
2577:
2530:
2510:
2490:
2470:
2450:
2430:
2263:
2168:
2148:
2124:
2104:
2084:
2064:
2044:
2024:
2004:
1943:
1923:
1903:
1883:
1863:
1843:
1823:
1803:
1782:
1734:
1714:
1694:
1674:
1516:
1496:
1476:
1456:
1436:
1416:
1267:
1243:
1060:
1017:
997:
977:
957:
937:
894:
874:
795:
775:
755:
735:
647:
595:
575:
555:
532:
512:
492:
472:
452:
432:
412:
392:
372:
352:
332:
206:
186:
166:
146:
126:
106:
86:
66:
6411:
6385:
3321:
3426:
3207:
2170:. The last two nodes are node 7 and node 8. Therefore, merge edge (7,8). The minimum cut is 5, so remain the minimum as 5.
1547:
2182:
To prove the correctness of this algorithm, we need to prove that the cut given by
MinimumCutPhase is in fact a minimum
6432:
800:
3799:
1269:
by merging the two vertices (s, t) added last (the value of "cut-of-the-phase" is the value of minimum s, t cut.)
6427:
6296:
2210:
cut of the graph, where s and t are the two vertices last added in the phase. Therefore, a lemma is shown below:
4041:
3521:
2783:
2532:
are in opposite sides of the cut. We prove the lemma by induction on the set of active vertices. We define
1163:
2412:. Observe that a single run of MinimumCutPhase gives us an ordering of all the vertices in the graph (where
2272:
4135:
For the further improvement, the key is to make it easy to select the next vertex to be added to the set
4534:
3964:
2877:
652:
3585:
2688:
2721:
2649:
223:
2368:
1249:
store the cut in which the last remaining vertex is by itself (the "cut-of-the-phase") shrink
1065:
36:
6331:
4531:
amortized time. Thus, the time we need for this key step that dominates the rest of the phase, is
2933:
2317:
2220:
2185:
1739:
4460:
2006:
and randomly selects node 2 as the starting node for this algorithm. In the
MinimumCutPhase, set
213:
6368:
4155:, the most tightly connected vertex. During execution of a phase, all vertices that are not in
2976:
1521:
1199:
241:
19:
3676:
3640:
1315:
285:
1353:
1275:
1126:
4218:
4038:
Therefore, the overall running time should be the product of two phase complexity, which is
1624:
227:
44:
3917:
3057:
3030:
2850:
2602:
2535:
2130:
In step 2, starting from node 2, the heaviest edge is (2,1+5), thus node 1+5 is put in set
688:
600:
4505:
4426:
4396:
1948:
208:
cuts. The minimum cut found in all phases will be the minimum weighted cut of the graph.
4393:, if it exists. As this is done exactly once for every edge, overall we have to perform
4373:
2345:
1022:
899:
4454:
4353:
4333:
4313:
4293:
4273:
4253:
4198:
4178:
4158:
4138:
3881:
3776:
3756:
3736:
3716:
3184:
3164:
3144:
3124:
3104:
3084:
3010:
2760:
2629:
2582:
2562:
2515:
2495:
2475:
2455:
2435:
2415:
2248:
2153:
2133:
2109:
2089:
2069:
2049:
2029:
2009:
1989:
1928:
1908:
1888:
1868:
1848:
1828:
1808:
1788:
1767:
1719:
1699:
1679:
1659:
1501:
1481:
1461:
1441:
1421:
1401:
1252:
1228:
1045:
1002:
982:
962:
942:
922:
879:
859:
780:
760:
740:
720:
632:
580:
560:
540:
517:
497:
477:
457:
437:
417:
397:
377:
357:
337:
317:
191:
171:
151:
131:
111:
91:
71:
51:
6421:
6348:
2066:
contains node 2 and node 3, the heaviest edge is (3,4), thus node 4 is added to set
3907:
2086:. By following this procedure, the last two nodes are node 5 and node 1, which are
28:
217:
is a partition of the vertices of a graph into two non-empty, disjoint subsets. A
1972:
218:
40:
2026:
only has node 2, the heaviest edge is edge (2,3), so node 3 is added into set
1418:
of the graphs vertices grows starting with an arbitrary single vertex until
3954:, which is called on graphs with decreasing number of vertices and edges.
1391:
the cut-of-the-phase is lighter than the current minimum cut
2874:
be the first active vertex. By the definition of these two quantities,
4622:// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.
4175:
reside in a priority queue based on a key field. The key of a vertex
3733:
is always an active vertex since the last cut of the phase separates
4195:
is the sum of the weights of the edges connecting it to the current
4614:
797:. Therefore, the global min-cut can be found by checking the graph
1398:
The algorithm works in phases. In the
MinimumCutPhase, the subset
18:
2472:
are the two vertices added last in the phase). We say the vertex
6349:"Lecture notes for Analysis of Algorithms": Global minimum cuts"
128:
chosen at its will. Then the algorithm shrinks the edge between
230:, since the minimum cut is a bottleneck in a graph or network.
4310:
has to be deleted from the queue, and the key of every vertex
6414:- a Java library that implements the Stoer–Wagner algorithm
3416:{\displaystyle w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)}
1983:
This section refers to Figs. 1–6 in the original paper.
3878:
Therefore, the cut of the phase is at most as heavy as
959:
are connected by an edge then this edge disappears. If
3508:{\displaystyle w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})}
3308:{\displaystyle w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)}
1518:. This procedure can be formally shown as: add vertex
1395:
store the cut-of-the-phase as the current minimum cut
4537:
4508:
4463:
4429:
4399:
4376:
4356:
4336:
4316:
4296:
4276:
4256:
4221:
4201:
4181:
4161:
4141:
4044:
3967:
3920:
3884:
3802:
3779:
3759:
3739:
3719:
3679:
3643:
3588:
3524:
3429:
3324:
3210:
3187:
3167:
3147:
3127:
3107:
3087:
3060:
3033:
3013:
2979:
2936:
2880:
2853:
2786:
2763:
2724:
2691:
2652:
2632:
2605:
2585:
2565:
2538:
2518:
2498:
2478:
2458:
2438:
2418:
2371:
2348:
2320:
2275:
2251:
2223:
2188:
2156:
2136:
2112:
2092:
2072:
2052:
2032:
2012:
1992:
1951:
1931:
1911:
1891:
1871:
1851:
1831:
1811:
1791:
1770:
1742:
1722:
1702:
1682:
1662:
1627:
1550:
1524:
1504:
1484:
1464:
1444:
1424:
1404:
1356:
1318:
1278:
1255:
1231:
1202:
1166:
1129:
1068:
1048:
1025:
1005:
985:
965:
945:
925:
902:
882:
862:
803:
783:
763:
743:
723:
691:
655:
635:
603:
583:
563:
543:
520:
500:
480:
460:
440:
420:
400:
380:
360:
340:
320:
288:
244:
194:
174:
154:
134:
114:
94:
74:
54:
23:
A min-cut of a weighted graph having min-cut weight 4
6297:"Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1"
1656:is the sum of the weights of all the edges between
1614:{\displaystyle w(A,z)=\max\{w(A,y)\mid y\notin A\}}
4597:
4523:
4494:
4445:
4415:
4385:
4362:
4342:
4322:
4302:
4282:
4262:
4242:
4207:
4187:
4167:
4147:
4124:
4027:
3942:
3890:
3867:
3785:
3765:
3745:
3725:
3701:
3665:
3629:
3574:
3507:
3415:
3307:
3193:
3173:
3153:
3133:
3113:
3093:
3073:
3046:
3019:
2999:
2965:
2922:
2866:
2836:
2769:
2749:
2710:
2677:
2638:
2618:
2591:
2571:
2551:
2524:
2504:
2484:
2464:
2444:
2424:
2404:
2357:
2334:
2306:
2257:
2237:
2202:
2162:
2142:
2118:
2098:
2078:
2058:
2038:
2018:
1998:
1963:
1937:
1917:
1897:
1877:
1857:
1837:
1817:
1797:
1776:
1756:
1728:
1708:
1688:
1668:
1648:
1613:
1536:
1510:
1490:
1470:
1450:
1430:
1410:
1380:
1340:
1302:
1261:
1237:
1217:
1186:
1153:
1110:
1054:
1034:
1019:, then the weight of the edge from the new vertex
1011:
991:
971:
951:
931:
911:
888:
868:
848:
789:
769:
749:
729:
709:
677:
641:
621:
589:
569:
549:
526:
506:
486:
466:
446:
426:
406:
386:
366:
346:
326:
306:
274:
200:
180:
160:
140:
120:
100:
80:
60:
3101:. Therefore, as shown above, for active vertices
2365:be the cut given by the phase. We must show that
777:belong to the same side of the global min-cut of
222:minimum cut problem is always discussed with the
1572:
6369:"The minimum cut algorithm of Stoer and Wagner"
4502:amortized time and an IncreaseKey operation in
1458:. In each step, the vertex which is outside of
849:{\displaystyle G\cup \{st\}/\left\{s,t\right\}}
4617:implementation of the Stoer–Wagner algorithm.
4370:has to be increased by the weight of the edge
3709:(and other edges are of non-negative weights)
1986:The graph in step 1 shows the original graph
282:be a weighted undirected graph. Suppose that
8:
6386:"KTH Algorithm Competition Template Library"
3868:{\displaystyle w(A_{t},t)\leq w(C_{t})=w(C)}
2744:
2738:
2672:
2666:
1696:. So, in a single phase, a pair of vertices
1608:
1575:
856:, which is the graph after merging vertices
819:
810:
685:, there are two possible situations: either
5006:// O(V^2) -> O(E log V) with prio. queue
4290:we have to perform an update of the queue.
3054:, and the edges between these vertices and
4457:we can perform an ExtractMax operation in
3914:is equal to the added running time of the
4587:
4579:
4568:
4560:
4552:
4544:
4536:
4507:
4484:
4476:
4462:
4438:
4430:
4428:
4408:
4400:
4398:
4375:
4355:
4335:
4315:
4295:
4275:
4255:
4220:
4200:
4180:
4160:
4140:
4125:{\displaystyle O(|V||E|+|V|^{2}\log |V|)}
4114:
4106:
4094:
4089:
4080:
4072:
4064:
4059:
4051:
4043:
4017:
4009:
3998:
3990:
3982:
3974:
3966:
3929:
3921:
3919:
3883:
3841:
3813:
3801:
3778:
3758:
3738:
3718:
3690:
3678:
3654:
3642:
3612:
3599:
3587:
3563:
3535:
3523:
3496:
3468:
3440:
3428:
3398:
3385:
3363:
3335:
3323:
3290:
3277:
3249:
3221:
3209:
3186:
3166:
3146:
3126:
3106:
3086:
3065:
3059:
3038:
3032:
3012:
2989:
2984:
2978:
2952:
2947:
2935:
2911:
2896:
2891:
2879:
2858:
2852:
2825:
2797:
2785:
2762:
2729:
2723:
2696:
2690:
2657:
2651:
2631:
2610:
2604:
2584:
2564:
2543:
2537:
2517:
2497:
2477:
2457:
2437:
2417:
2370:
2347:
2324:
2319:
2291:
2274:
2250:
2227:
2222:
2192:
2187:
2155:
2135:
2111:
2091:
2071:
2051:
2031:
2011:
1991:
1950:
1930:
1910:
1890:
1870:
1850:
1830:
1810:
1790:
1769:
1746:
1741:
1721:
1701:
1681:
1661:
1626:
1549:
1523:
1503:
1483:
1463:
1443:
1423:
1403:
1355:
1327:
1319:
1317:
1277:
1254:
1230:
1201:
1165:
1128:
1067:
1047:
1024:
1004:
984:
964:
944:
924:
901:
881:
861:
822:
802:
782:
762:
742:
722:
690:
654:
634:
602:
582:
562:
542:
519:
499:
479:
459:
439:
419:
399:
379:
359:
339:
319:
287:
243:
193:
173:
153:
133:
113:
93:
73:
53:
6288:
3575:{\displaystyle w(A_{u},u)\leq w(C_{u})}
2837:{\displaystyle w(A_{v},v)\leq w(C_{v})}
1187:{\displaystyle A\gets \left\{a\right\}}
226:, to explore the maximum capacity of a
1245:the most tightly connected vertex
4453:IncreaseKey operations. By using the
3773:by definition, for any active vertex
2307:{\displaystyle C=(X,{\overline {X}})}
7:
6363:
6361:
6343:
6341:
6326:
6324:
6322:
6320:
6318:
6316:
2217:: MinimumCutPhase returns a minimum
537:This algorithm starts by finding an
3961:, a single run of it needs at most
2757:. We prove, for each active vertex
16:Recursive algorithm in graph theory
4598:{\displaystyle O(|E|+|V|\log |V|)}
4028:{\displaystyle O(|E|+|V|\log |V|)}
2923:{\displaystyle w(A_{v_{0}},v_{0})}
1885:. If not, then the minimum cut of
1478:, but most tightly connected with
678:{\displaystyle \left\{s,t\right\}}
234:Stoer–Wagner minimum cut algorithm
14:
3081:are the edges that cross the cut
2512:and the vertex added just before
1118:. The algorithm is described as:
3630:{\displaystyle w(A_{u}-A_{v},u)}
3007:is simply all vertices added to
2711:{\displaystyle C_{v}\subseteq C}
2559:as the set of vertices added to
2750:{\displaystyle A_{v}\cup \{v\}}
2678:{\displaystyle A_{v}\cup \{v\}}
999:both have edges to some vertex
4592:
4588:
4580:
4569:
4561:
4553:
4545:
4541:
4518:
4512:
4489:
4485:
4477:
4467:
4439:
4431:
4409:
4401:
4237:
4225:
4119:
4115:
4107:
4090:
4081:
4073:
4065:
4060:
4052:
4048:
4022:
4018:
4010:
3999:
3991:
3983:
3975:
3971:
3930:
3922:
3862:
3856:
3847:
3834:
3825:
3806:
3696:
3683:
3660:
3647:
3624:
3592:
3569:
3556:
3547:
3528:
3502:
3489:
3480:
3461:
3452:
3433:
3410:
3378:
3369:
3356:
3347:
3328:
3302:
3270:
3261:
3242:
3233:
3214:
2960:
2940:
2917:
2884:
2831:
2818:
2809:
2790:
2405:{\displaystyle W(C)\geq W(CP)}
2399:
2390:
2381:
2375:
2301:
2282:
1643:
1631:
1593:
1581:
1566:
1554:
1375:
1357:
1328:
1320:
1297:
1279:
1170:
1148:
1130:
1105:
1093:
1084:
1072:
704:
692:
616:
604:
269:
251:
1:
1111:{\displaystyle w(s,v)+w(t,v)}
6332:"A Simple Min-Cut Algorithm"
2966:{\displaystyle w(C_{v_{0}})}
2335:{\displaystyle s{\text{-}}t}
2296:
2238:{\displaystyle s{\text{-}}t}
2203:{\displaystyle s{\text{-}}t}
1757:{\displaystyle s{\text{-}}t}
4495:{\displaystyle O(\log |V|)}
2646:with both of their ends in
6449:
2626:to be the set of edges in
3000:{\displaystyle A_{v_{0}}}
1537:{\displaystyle z\notin A}
1218:{\displaystyle \ A\neq V}
919:. During the merging, if
275:{\displaystyle G=(V,E,w)}
5366:
4619:
3702:{\displaystyle w(C_{v})}
3666:{\displaystyle w(C_{u})}
1341:{\displaystyle |V|>1}
314:. The cut is called an
307:{\displaystyle s,t\in V}
1381:{\displaystyle (G,w,a)}
1303:{\displaystyle (G,w,a)}
1154:{\displaystyle (G,w,a)}
717:is a global min-cut of
6412:StoerWagnerMinCut.java
4599:
4525:
4496:
4447:
4417:
4387:
4364:
4344:
4324:
4304:
4284:
4264:
4244:
4243:{\displaystyle w(A,v)}
4209:
4189:
4169:
4149:
4126:
4029:
3944:
3892:
3876:
3869:
3787:
3767:
3747:
3727:
3711:
3703:
3667:
3631:
3576:
3516:
3509:
3417:
3316:
3309:
3195:
3175:
3155:
3135:
3115:
3095:
3075:
3048:
3021:
3001:
2967:
2924:
2868:
2845:
2838:
2771:
2751:
2718:is the cut induced by
2712:
2679:
2640:
2620:
2593:
2573:
2553:
2526:
2506:
2486:
2466:
2446:
2426:
2406:
2359:
2336:
2308:
2267:
2259:
2239:
2204:
2164:
2144:
2120:
2100:
2080:
2060:
2040:
2020:
2000:
1965:
1939:
1919:
1899:
1879:
1859:
1839:
1819:
1799:
1778:
1758:
1730:
1710:
1690:
1670:
1650:
1649:{\displaystyle w(A,y)}
1615:
1538:
1512:
1492:
1472:
1452:
1432:
1412:
1382:
1342:
1304:
1263:
1239:
1219:
1188:
1155:
1112:
1056:
1036:
1013:
993:
973:
953:
933:
913:
890:
870:
850:
791:
771:
751:
731:
711:
679:
643:
623:
591:
571:
551:
528:
508:
488:
468:
448:
428:
408:
388:
368:
354:cut if exactly one of
348:
328:
308:
276:
202:
182:
162:
142:
122:
102:
82:
62:
33:Stoer–Wagner algorithm
24:
4637:<bits/stdc++.h>
4600:
4526:
4497:
4448:
4418:
4388:
4365:
4345:
4325:
4305:
4285:
4265:
4245:
4210:
4190:
4170:
4150:
4127:
4030:
3945:
3943:{\displaystyle |V|-1}
3893:
3870:
3795:
3788:
3768:
3748:
3728:
3704:
3668:
3632:
3577:
3517:
3510:
3418:
3317:
3310:
3203:
3196:
3176:
3156:
3136:
3116:
3096:
3076:
3074:{\displaystyle v_{0}}
3049:
3047:{\displaystyle v_{0}}
3022:
3002:
2968:
2925:
2869:
2867:{\displaystyle v_{0}}
2839:
2779:
2772:
2752:
2713:
2680:
2641:
2621:
2619:{\displaystyle C_{v}}
2594:
2574:
2554:
2552:{\displaystyle A_{v}}
2527:
2507:
2487:
2467:
2447:
2427:
2407:
2360:
2337:
2309:
2260:
2240:
2212:
2205:
2165:
2145:
2121:
2101:
2081:
2061:
2041:
2021:
2001:
1966:
1940:
1920:
1900:
1880:
1860:
1840:
1820:
1800:
1779:
1759:
1731:
1711:
1691:
1671:
1651:
1616:
1539:
1513:
1493:
1473:
1453:
1433:
1413:
1383:
1343:
1305:
1264:
1240:
1220:
1189:
1156:
1113:
1057:
1037:
1014:
994:
974:
954:
934:
914:
891:
871:
851:
792:
772:
752:
732:
712:
710:{\displaystyle (S,T)}
680:
644:
624:
622:{\displaystyle (S,T)}
597:, and an s-t min-cut
592:
572:
552:
529:
509:
489:
469:
449:
429:
414:. The minimal cut of
409:
389:
369:
349:
329:
309:
277:
203:
183:
163:
143:
123:
103:
88:cut for two vertices
83:
63:
22:
4535:
4524:{\displaystyle O(1)}
4506:
4461:
4427:
4397:
4374:
4354:
4334:
4314:
4294:
4274:
4254:
4250:. Whenever a vertex
4219:
4199:
4179:
4159:
4139:
4042:
3965:
3918:
3882:
3800:
3777:
3757:
3737:
3717:
3677:
3641:
3586:
3522:
3427:
3322:
3208:
3185:
3165:
3145:
3125:
3105:
3085:
3058:
3031:
3011:
2977:
2934:
2878:
2851:
2784:
2761:
2722:
2689:
2650:
2630:
2603:
2583:
2563:
2536:
2516:
2496:
2476:
2456:
2436:
2416:
2369:
2346:
2318:
2273:
2249:
2221:
2186:
2178:Proof of correctness
2154:
2134:
2110:
2090:
2070:
2050:
2030:
2010:
1990:
1949:
1929:
1909:
1889:
1869:
1865:is a minimum cut of
1849:
1829:
1809:
1789:
1768:
1740:
1720:
1700:
1680:
1660:
1625:
1548:
1522:
1502:
1498:is added to the set
1482:
1462:
1442:
1422:
1402:
1354:
1316:
1276:
1253:
1229:
1200:
1164:
1127:
1066:
1046:
1023:
1003:
983:
963:
943:
923:
900:
880:
860:
801:
781:
761:
741:
721:
689:
653:
633:
601:
581:
561:
541:
518:
498:
478:
458:
438:
418:
398:
378:
358:
338:
318:
286:
242:
224:maximum flow problem
192:
172:
152:
132:
112:
92:
72:
52:
4613:Below is a concise
4446:{\displaystyle |E|}
4416:{\displaystyle |V|}
1975:can be determined.
1964:{\displaystyle n-1}
37:recursive algorithm
6433:Graph connectivity
4595:
4521:
4492:
4443:
4413:
4386:{\displaystyle vw}
4383:
4360:
4340:
4320:
4300:
4280:
4260:
4240:
4205:
4185:
4165:
4145:
4122:
4025:
3940:
3888:
3865:
3783:
3763:
3743:
3723:
3699:
3663:
3627:
3572:
3505:
3413:
3305:
3191:
3171:
3151:
3131:
3111:
3091:
3071:
3044:
3017:
2997:
2963:
2920:
2864:
2834:
2767:
2747:
2708:
2675:
2636:
2616:
2589:
2569:
2549:
2522:
2502:
2482:
2462:
2442:
2422:
2402:
2358:{\displaystyle CP}
2355:
2332:
2304:
2255:
2235:
2200:
2160:
2140:
2116:
2096:
2076:
2056:
2036:
2016:
1996:
1961:
1935:
1915:
1895:
1875:
1855:
1835:
1815:
1795:
1774:
1754:
1726:
1706:
1686:
1666:
1646:
1611:
1534:
1508:
1488:
1468:
1448:
1428:
1408:
1378:
1338:
1300:
1259:
1235:
1215:
1184:
1151:
1108:
1052:
1035:{\displaystyle st}
1032:
1009:
989:
969:
949:
929:
912:{\displaystyle st}
909:
896:into a new vertex
886:
866:
846:
787:
767:
747:
727:
707:
675:
639:
619:
587:
567:
547:
524:
504:
484:
474:cut is called the
464:
444:
424:
404:
384:
364:
344:
324:
304:
272:
198:
178:
168:to search for non
158:
138:
118:
98:
78:
58:
25:
4363:{\displaystyle v}
4343:{\displaystyle A}
4323:{\displaystyle w}
4303:{\displaystyle v}
4283:{\displaystyle A}
4263:{\displaystyle v}
4208:{\displaystyle A}
4188:{\displaystyle V}
4168:{\displaystyle A}
4148:{\displaystyle A}
3910:of the algorithm
3891:{\displaystyle C}
3786:{\displaystyle t}
3766:{\displaystyle t}
3746:{\displaystyle s}
3726:{\displaystyle t}
3194:{\displaystyle u}
3174:{\displaystyle A}
3154:{\displaystyle v}
3134:{\displaystyle u}
3114:{\displaystyle v}
3094:{\displaystyle C}
3020:{\displaystyle A}
2770:{\displaystyle v}
2639:{\displaystyle C}
2592:{\displaystyle v}
2572:{\displaystyle A}
2525:{\displaystyle v}
2505:{\displaystyle v}
2485:{\displaystyle v}
2465:{\displaystyle t}
2445:{\displaystyle s}
2432:is the first and
2425:{\displaystyle a}
2327:
2299:
2258:{\displaystyle G}
2230:
2195:
2163:{\displaystyle A}
2143:{\displaystyle A}
2119:{\displaystyle t}
2099:{\displaystyle s}
2079:{\displaystyle A}
2059:{\displaystyle A}
2039:{\displaystyle A}
2019:{\displaystyle A}
1999:{\displaystyle G}
1938:{\displaystyle t}
1918:{\displaystyle s}
1898:{\displaystyle G}
1878:{\displaystyle G}
1858:{\displaystyle C}
1838:{\displaystyle t}
1818:{\displaystyle s}
1798:{\displaystyle G}
1777:{\displaystyle C}
1749:
1729:{\displaystyle t}
1709:{\displaystyle s}
1689:{\displaystyle y}
1669:{\displaystyle A}
1511:{\displaystyle A}
1491:{\displaystyle A}
1471:{\displaystyle A}
1451:{\displaystyle V}
1431:{\displaystyle A}
1411:{\displaystyle A}
1262:{\displaystyle G}
1238:{\displaystyle A}
1205:
1055:{\displaystyle v}
1012:{\displaystyle v}
992:{\displaystyle t}
972:{\displaystyle s}
952:{\displaystyle t}
932:{\displaystyle s}
889:{\displaystyle t}
869:{\displaystyle s}
790:{\displaystyle G}
770:{\displaystyle t}
750:{\displaystyle s}
730:{\displaystyle G}
642:{\displaystyle G}
590:{\displaystyle V}
570:{\displaystyle t}
550:{\displaystyle s}
527:{\displaystyle G}
507:{\displaystyle t}
487:{\displaystyle s}
467:{\displaystyle t}
447:{\displaystyle s}
427:{\displaystyle G}
407:{\displaystyle S}
387:{\displaystyle t}
367:{\displaystyle s}
347:{\displaystyle t}
327:{\displaystyle s}
201:{\displaystyle t}
181:{\displaystyle s}
161:{\displaystyle t}
141:{\displaystyle s}
121:{\displaystyle t}
101:{\displaystyle s}
81:{\displaystyle t}
61:{\displaystyle s}
6440:
6428:Graph algorithms
6400:
6399:
6397:
6396:
6382:
6376:
6375:
6373:
6365:
6356:
6355:
6353:
6345:
6336:
6335:
6328:
6311:
6310:
6308:
6307:
6293:
6279:
6276:
6273:
6270:
6267:
6264:
6261:
6258:
6255:
6252:
6249:
6246:
6243:
6240:
6237:
6234:
6231:
6228:
6225:
6222:
6219:
6216:
6213:
6210:
6207:
6204:
6201:
6198:
6195:
6192:
6189:
6186:
6183:
6180:
6177:
6174:
6171:
6168:
6165:
6162:
6159:
6156:
6153:
6150:
6147:
6144:
6141:
6138:
6135:
6132:
6129:
6126:
6123:
6120:
6117:
6114:
6111:
6108:
6105:
6102:
6099:
6096:
6093:
6090:
6087:
6084:
6081:
6078:
6075:
6072:
6069:
6066:
6063:
6060:
6057:
6054:
6051:
6048:
6045:
6042:
6039:
6036:
6033:
6030:
6027:
6024:
6021:
6018:
6015:
6012:
6009:
6006:
6003:
6000:
5997:
5994:
5991:
5988:
5985:
5982:
5979:
5976:
5973:
5970:
5967:
5964:
5961:
5958:
5955:
5952:
5949:
5946:
5943:
5940:
5937:
5934:
5931:
5928:
5925:
5922:
5919:
5916:
5913:
5910:
5907:
5904:
5901:
5898:
5895:
5892:
5889:
5886:
5883:
5880:
5877:
5874:
5871:
5868:
5865:
5862:
5859:
5856:
5853:
5850:
5847:
5844:
5841:
5838:
5835:
5832:
5829:
5826:
5823:
5820:
5817:
5814:
5811:
5808:
5805:
5802:
5799:
5796:
5793:
5790:
5787:
5784:
5781:
5778:
5775:
5772:
5769:
5766:
5763:
5760:
5757:
5754:
5751:
5748:
5745:
5742:
5739:
5736:
5733:
5730:
5727:
5724:
5721:
5718:
5715:
5712:
5709:
5706:
5703:
5700:
5697:
5694:
5691:
5688:
5685:
5682:
5679:
5676:
5673:
5670:
5667:
5664:
5661:
5658:
5655:
5652:
5649:
5646:
5643:
5640:
5637:
5634:
5631:
5628:
5625:
5622:
5619:
5616:
5613:
5610:
5607:
5604:
5601:
5598:
5595:
5592:
5589:
5586:
5583:
5580:
5577:
5574:
5571:
5568:
5565:
5562:
5559:
5556:
5553:
5550:
5547:
5544:
5541:
5538:
5535:
5532:
5529:
5526:
5523:
5520:
5517:
5514:
5511:
5508:
5505:
5502:
5499:
5496:
5493:
5490:
5487:
5484:
5481:
5478:
5475:
5472:
5469:
5466:
5463:
5460:
5457:
5454:
5451:
5448:
5445:
5442:
5439:
5436:
5433:
5430:
5427:
5424:
5421:
5418:
5415:
5412:
5409:
5406:
5403:
5400:
5397:
5394:
5391:
5388:
5385:
5382:
5379:
5376:
5373:
5370:
5361:
5358:
5355:
5352:
5349:
5346:
5343:
5340:
5337:
5334:
5331:
5328:
5325:
5322:
5319:
5316:
5313:
5310:
5307:
5304:
5301:
5298:
5295:
5292:
5289:
5286:
5283:
5280:
5277:
5274:
5271:
5268:
5265:
5262:
5259:
5256:
5253:
5250:
5247:
5244:
5241:
5238:
5235:
5232:
5229:
5226:
5223:
5220:
5217:
5214:
5211:
5208:
5205:
5202:
5199:
5196:
5193:
5190:
5187:
5184:
5181:
5178:
5175:
5172:
5169:
5166:
5163:
5160:
5157:
5154:
5151:
5148:
5145:
5142:
5139:
5136:
5133:
5130:
5127:
5124:
5121:
5118:
5115:
5112:
5109:
5106:
5103:
5100:
5097:
5094:
5091:
5088:
5085:
5082:
5079:
5076:
5073:
5070:
5067:
5064:
5061:
5058:
5055:
5052:
5049:
5046:
5043:
5040:
5037:
5034:
5031:
5028:
5025:
5022:
5019:
5016:
5013:
5010:
5007:
5004:
5001:
4998:
4995:
4992:
4989:
4986:
4983:
4980:
4977:
4974:
4971:
4968:
4965:
4962:
4959:
4956:
4953:
4950:
4947:
4944:
4941:
4938:
4935:
4932:
4929:
4926:
4923:
4920:
4917:
4914:
4911:
4908:
4905:
4902:
4899:
4896:
4893:
4890:
4887:
4884:
4881:
4878:
4875:
4872:
4869:
4866:
4863:
4860:
4857:
4854:
4851:
4848:
4845:
4842:
4839:
4836:
4833:
4830:
4827:
4824:
4821:
4818:
4815:
4812:
4809:
4806:
4803:
4800:
4797:
4794:
4791:
4788:
4785:
4782:
4779:
4776:
4773:
4770:
4767:
4764:
4761:
4758:
4755:
4752:
4749:
4746:
4743:
4740:
4737:
4734:
4731:
4728:
4725:
4722:
4719:
4716:
4713:
4710:
4707:
4704:
4701:
4698:
4695:
4692:
4689:
4686:
4683:
4680:
4677:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4650:
4647:
4644:
4641:
4638:
4635:
4632:
4629:
4628:// Running time:
4626:
4623:
4604:
4602:
4601:
4596:
4591:
4583:
4572:
4564:
4556:
4548:
4530:
4528:
4527:
4522:
4501:
4499:
4498:
4493:
4488:
4480:
4452:
4450:
4449:
4444:
4442:
4434:
4422:
4420:
4419:
4414:
4412:
4404:
4392:
4390:
4389:
4384:
4369:
4367:
4366:
4361:
4349:
4347:
4346:
4341:
4329:
4327:
4326:
4321:
4309:
4307:
4306:
4301:
4289:
4287:
4286:
4281:
4269:
4267:
4266:
4261:
4249:
4247:
4246:
4241:
4214:
4212:
4211:
4206:
4194:
4192:
4191:
4186:
4174:
4172:
4171:
4166:
4154:
4152:
4151:
4146:
4131:
4129:
4128:
4123:
4118:
4110:
4099:
4098:
4093:
4084:
4076:
4068:
4063:
4055:
4034:
4032:
4031:
4026:
4021:
4013:
4002:
3994:
3986:
3978:
3949:
3947:
3946:
3941:
3933:
3925:
3897:
3895:
3894:
3889:
3874:
3872:
3871:
3866:
3846:
3845:
3818:
3817:
3792:
3790:
3789:
3784:
3772:
3770:
3769:
3764:
3752:
3750:
3749:
3744:
3732:
3730:
3729:
3724:
3708:
3706:
3705:
3700:
3695:
3694:
3672:
3670:
3669:
3664:
3659:
3658:
3636:
3634:
3633:
3628:
3617:
3616:
3604:
3603:
3581:
3579:
3578:
3573:
3568:
3567:
3540:
3539:
3514:
3512:
3511:
3506:
3501:
3500:
3473:
3472:
3445:
3444:
3422:
3420:
3419:
3414:
3403:
3402:
3390:
3389:
3368:
3367:
3340:
3339:
3314:
3312:
3311:
3306:
3295:
3294:
3282:
3281:
3254:
3253:
3226:
3225:
3200:
3198:
3197:
3192:
3180:
3178:
3177:
3172:
3160:
3158:
3157:
3152:
3140:
3138:
3137:
3132:
3120:
3118:
3117:
3112:
3100:
3098:
3097:
3092:
3080:
3078:
3077:
3072:
3070:
3069:
3053:
3051:
3050:
3045:
3043:
3042:
3026:
3024:
3023:
3018:
3006:
3004:
3003:
2998:
2996:
2995:
2994:
2993:
2973:are equivalent.
2972:
2970:
2969:
2964:
2959:
2958:
2957:
2956:
2929:
2927:
2926:
2921:
2916:
2915:
2903:
2902:
2901:
2900:
2873:
2871:
2870:
2865:
2863:
2862:
2843:
2841:
2840:
2835:
2830:
2829:
2802:
2801:
2776:
2774:
2773:
2768:
2756:
2754:
2753:
2748:
2734:
2733:
2717:
2715:
2714:
2709:
2701:
2700:
2684:
2682:
2681:
2676:
2662:
2661:
2645:
2643:
2642:
2637:
2625:
2623:
2622:
2617:
2615:
2614:
2598:
2596:
2595:
2590:
2578:
2576:
2575:
2570:
2558:
2556:
2555:
2550:
2548:
2547:
2531:
2529:
2528:
2523:
2511:
2509:
2508:
2503:
2491:
2489:
2488:
2483:
2471:
2469:
2468:
2463:
2451:
2449:
2448:
2443:
2431:
2429:
2428:
2423:
2411:
2409:
2408:
2403:
2364:
2362:
2361:
2356:
2341:
2339:
2338:
2333:
2328:
2325:
2314:be an arbitrary
2313:
2311:
2310:
2305:
2300:
2292:
2264:
2262:
2261:
2256:
2244:
2242:
2241:
2236:
2231:
2228:
2209:
2207:
2206:
2201:
2196:
2193:
2169:
2167:
2166:
2161:
2149:
2147:
2146:
2141:
2125:
2123:
2122:
2117:
2105:
2103:
2102:
2097:
2085:
2083:
2082:
2077:
2065:
2063:
2062:
2057:
2045:
2043:
2042:
2037:
2025:
2023:
2022:
2017:
2005:
2003:
2002:
1997:
1970:
1968:
1967:
1962:
1944:
1942:
1941:
1936:
1924:
1922:
1921:
1916:
1904:
1902:
1901:
1896:
1884:
1882:
1881:
1876:
1864:
1862:
1861:
1856:
1844:
1842:
1841:
1836:
1824:
1822:
1821:
1816:
1804:
1802:
1801:
1796:
1783:
1781:
1780:
1775:
1763:
1761:
1760:
1755:
1750:
1747:
1735:
1733:
1732:
1727:
1715:
1713:
1712:
1707:
1695:
1693:
1692:
1687:
1675:
1673:
1672:
1667:
1655:
1653:
1652:
1647:
1620:
1618:
1617:
1612:
1543:
1541:
1540:
1535:
1517:
1515:
1514:
1509:
1497:
1495:
1494:
1489:
1477:
1475:
1474:
1469:
1457:
1455:
1454:
1449:
1437:
1435:
1434:
1429:
1417:
1415:
1414:
1409:
1387:
1385:
1384:
1379:
1347:
1345:
1344:
1339:
1331:
1323:
1309:
1307:
1306:
1301:
1268:
1266:
1265:
1260:
1244:
1242:
1241:
1236:
1224:
1222:
1221:
1216:
1203:
1193:
1191:
1190:
1185:
1183:
1160:
1158:
1157:
1152:
1117:
1115:
1114:
1109:
1061:
1059:
1058:
1053:
1041:
1039:
1038:
1033:
1018:
1016:
1015:
1010:
998:
996:
995:
990:
978:
976:
975:
970:
958:
956:
955:
950:
938:
936:
935:
930:
918:
916:
915:
910:
895:
893:
892:
887:
875:
873:
872:
867:
855:
853:
852:
847:
845:
841:
826:
796:
794:
793:
788:
776:
774:
773:
768:
756:
754:
753:
748:
736:
734:
733:
728:
716:
714:
713:
708:
684:
682:
681:
676:
674:
670:
648:
646:
645:
640:
628:
626:
625:
620:
596:
594:
593:
588:
576:
574:
573:
568:
556:
554:
553:
548:
533:
531:
530:
525:
513:
511:
510:
505:
493:
491:
490:
485:
473:
471:
470:
465:
453:
451:
450:
445:
434:that is also an
433:
431:
430:
425:
413:
411:
410:
405:
393:
391:
390:
385:
373:
371:
370:
365:
353:
351:
350:
345:
333:
331:
330:
325:
313:
311:
310:
305:
281:
279:
278:
273:
207:
205:
204:
199:
187:
185:
184:
179:
167:
165:
164:
159:
147:
145:
144:
139:
127:
125:
124:
119:
107:
105:
104:
99:
87:
85:
84:
79:
67:
65:
64:
59:
6448:
6447:
6443:
6442:
6441:
6439:
6438:
6437:
6418:
6417:
6408:
6403:
6394:
6392:
6384:
6383:
6379:
6371:
6367:
6366:
6359:
6351:
6347:
6346:
6339:
6330:
6329:
6314:
6305:
6303:
6295:
6294:
6290:
6286:
6281:
6280:
6277:
6274:
6271:
6268:
6265:
6262:
6259:
6256:
6253:
6250:
6247:
6244:
6241:
6238:
6235:
6232:
6229:
6226:
6223:
6220:
6217:
6214:
6211:
6208:
6205:
6202:
6199:
6196:
6193:
6190:
6187:
6184:
6181:
6178:
6175:
6172:
6169:
6166:
6163:
6160:
6157:
6154:
6151:
6148:
6145:
6142:
6139:
6136:
6133:
6130:
6127:
6124:
6121:
6118:
6115:
6112:
6109:
6106:
6103:
6100:
6097:
6094:
6091:
6088:
6085:
6082:
6079:
6076:
6073:
6070:
6067:
6064:
6061:
6058:
6055:
6052:
6049:
6046:
6043:
6040:
6037:
6034:
6031:
6028:
6025:
6022:
6019:
6016:
6013:
6010:
6007:
6004:
6001:
5998:
5995:
5992:
5989:
5986:
5983:
5980:
5977:
5974:
5971:
5968:
5965:
5962:
5959:
5956:
5953:
5950:
5947:
5944:
5941:
5938:
5935:
5932:
5929:
5926:
5923:
5920:
5917:
5914:
5911:
5908:
5905:
5902:
5899:
5896:
5893:
5890:
5887:
5884:
5881:
5878:
5875:
5872:
5869:
5866:
5863:
5860:
5857:
5854:
5851:
5848:
5845:
5842:
5839:
5836:
5833:
5830:
5827:
5824:
5821:
5818:
5815:
5812:
5809:
5806:
5803:
5800:
5797:
5794:
5791:
5788:
5785:
5782:
5779:
5776:
5773:
5770:
5767:
5764:
5761:
5758:
5755:
5752:
5749:
5746:
5743:
5740:
5737:
5734:
5731:
5728:
5725:
5722:
5719:
5716:
5713:
5710:
5707:
5704:
5701:
5698:
5695:
5692:
5689:
5686:
5683:
5680:
5677:
5674:
5671:
5668:
5665:
5662:
5659:
5656:
5653:
5650:
5647:
5644:
5641:
5638:
5635:
5632:
5629:
5626:
5623:
5620:
5617:
5614:
5611:
5608:
5605:
5602:
5599:
5596:
5593:
5590:
5587:
5584:
5581:
5578:
5575:
5572:
5569:
5566:
5563:
5560:
5557:
5554:
5551:
5548:
5545:
5542:
5539:
5536:
5533:
5530:
5527:
5524:
5521:
5518:
5515:
5512:
5509:
5506:
5503:
5500:
5497:
5494:
5491:
5488:
5485:
5482:
5479:
5476:
5473:
5470:
5467:
5464:
5461:
5458:
5455:
5452:
5449:
5446:
5443:
5440:
5437:
5434:
5431:
5428:
5425:
5422:
5419:
5416:
5413:
5410:
5407:
5404:
5401:
5398:
5395:
5392:
5389:
5386:
5383:
5380:
5377:
5374:
5371:
5368:
5363:
5362:
5359:
5356:
5353:
5350:
5347:
5344:
5341:
5338:
5335:
5332:
5329:
5326:
5323:
5320:
5317:
5314:
5311:
5308:
5305:
5302:
5299:
5296:
5293:
5290:
5287:
5284:
5281:
5278:
5275:
5272:
5269:
5266:
5263:
5260:
5257:
5254:
5251:
5248:
5245:
5242:
5239:
5236:
5233:
5230:
5227:
5224:
5221:
5218:
5215:
5212:
5209:
5206:
5203:
5200:
5197:
5194:
5191:
5188:
5185:
5182:
5179:
5176:
5173:
5170:
5167:
5164:
5161:
5158:
5155:
5152:
5149:
5146:
5143:
5140:
5137:
5134:
5131:
5128:
5125:
5122:
5119:
5116:
5113:
5110:
5107:
5104:
5101:
5098:
5095:
5092:
5089:
5086:
5083:
5080:
5077:
5074:
5071:
5068:
5065:
5062:
5059:
5056:
5053:
5050:
5047:
5044:
5041:
5038:
5035:
5032:
5029:
5026:
5023:
5020:
5017:
5014:
5011:
5008:
5005:
5002:
4999:
4996:
4993:
4990:
4987:
4984:
4981:
4978:
4975:
4972:
4969:
4966:
4963:
4960:
4957:
4954:
4951:
4948:
4945:
4942:
4939:
4936:
4933:
4930:
4927:
4924:
4921:
4918:
4915:
4912:
4909:
4906:
4903:
4900:
4897:
4894:
4891:
4888:
4885:
4882:
4879:
4876:
4873:
4870:
4867:
4864:
4861:
4858:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4834:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4795:
4792:
4789:
4786:
4783:
4780:
4777:
4774:
4771:
4768:
4765:
4762:
4759:
4756:
4753:
4750:
4747:
4744:
4741:
4738:
4735:
4732:
4729:
4726:
4723:
4720:
4717:
4714:
4711:
4708:
4705:
4702:
4699:
4696:
4693:
4690:
4687:
4684:
4681:
4678:
4675:
4672:
4669:
4666:
4663:
4660:
4657:
4654:
4651:
4648:
4645:
4642:
4639:
4636:
4633:
4631:// O(|V|^3)
4630:
4627:
4624:
4621:
4611:
4533:
4532:
4504:
4503:
4459:
4458:
4425:
4424:
4423:ExtractMax and
4395:
4394:
4372:
4371:
4352:
4351:
4350:, connected to
4332:
4331:
4312:
4311:
4292:
4291:
4272:
4271:
4252:
4251:
4217:
4216:
4197:
4196:
4177:
4176:
4157:
4156:
4137:
4136:
4088:
4040:
4039:
3963:
3962:
3959:MinimumCutPhase
3952:MinimumCutPhase
3916:
3915:
3904:
3902:Time complexity
3880:
3879:
3837:
3809:
3798:
3797:
3775:
3774:
3755:
3754:
3735:
3734:
3715:
3714:
3686:
3675:
3674:
3650:
3639:
3638:
3637:contributes to
3608:
3595:
3584:
3583:
3559:
3531:
3520:
3519:
3492:
3464:
3436:
3425:
3424:
3394:
3381:
3359:
3331:
3320:
3319:
3286:
3273:
3245:
3217:
3206:
3205:
3183:
3182:
3163:
3162:
3143:
3142:
3123:
3122:
3103:
3102:
3083:
3082:
3061:
3056:
3055:
3034:
3029:
3028:
3009:
3008:
2985:
2980:
2975:
2974:
2948:
2943:
2932:
2931:
2907:
2892:
2887:
2876:
2875:
2854:
2849:
2848:
2821:
2793:
2782:
2781:
2759:
2758:
2725:
2720:
2719:
2692:
2687:
2686:
2653:
2648:
2647:
2628:
2627:
2606:
2601:
2600:
2581:
2580:
2561:
2560:
2539:
2534:
2533:
2514:
2513:
2494:
2493:
2474:
2473:
2454:
2453:
2434:
2433:
2414:
2413:
2367:
2366:
2344:
2343:
2316:
2315:
2271:
2270:
2247:
2246:
2219:
2218:
2184:
2183:
2180:
2152:
2151:
2132:
2131:
2108:
2107:
2088:
2087:
2068:
2067:
2048:
2047:
2028:
2027:
2008:
2007:
1988:
1987:
1981:
1947:
1946:
1927:
1926:
1907:
1906:
1887:
1886:
1867:
1866:
1847:
1846:
1827:
1826:
1807:
1806:
1787:
1786:
1785:minimum cut of
1766:
1765:
1738:
1737:
1718:
1717:
1698:
1697:
1678:
1677:
1658:
1657:
1623:
1622:
1546:
1545:
1520:
1519:
1500:
1499:
1480:
1479:
1460:
1459:
1440:
1439:
1420:
1419:
1400:
1399:
1396:
1352:
1351:
1349:MinimumCutPhase
1314:
1313:
1274:
1273:
1251:
1250:
1227:
1226:
1198:
1197:
1173:
1162:
1161:
1125:
1124:
1122:MinimumCutPhase
1064:
1063:
1044:
1043:
1021:
1020:
1001:
1000:
981:
980:
961:
960:
941:
940:
921:
920:
898:
897:
878:
877:
858:
857:
831:
827:
799:
798:
779:
778:
759:
758:
739:
738:
719:
718:
687:
686:
660:
656:
651:
650:
649:. For any pair
631:
630:
599:
598:
579:
578:
559:
558:
539:
538:
516:
515:
496:
495:
476:
475:
456:
455:
436:
435:
416:
415:
396:
395:
376:
375:
356:
355:
336:
335:
316:
315:
284:
283:
240:
239:
236:
190:
189:
170:
169:
150:
149:
130:
129:
110:
109:
90:
89:
70:
69:
50:
49:
17:
12:
11:
5:
6446:
6444:
6436:
6435:
6430:
6420:
6419:
6416:
6415:
6407:
6406:External links
6404:
6402:
6401:
6377:
6357:
6337:
6312:
6287:
6285:
6282:
5367:
4620:
4610:
4607:
4594:
4590:
4586:
4582:
4578:
4575:
4571:
4567:
4563:
4559:
4555:
4551:
4547:
4543:
4540:
4520:
4517:
4514:
4511:
4491:
4487:
4483:
4479:
4475:
4472:
4469:
4466:
4455:Fibonacci heap
4441:
4437:
4433:
4411:
4407:
4403:
4382:
4379:
4359:
4339:
4319:
4299:
4279:
4259:
4239:
4236:
4233:
4230:
4227:
4224:
4204:
4184:
4164:
4144:
4121:
4117:
4113:
4109:
4105:
4102:
4097:
4092:
4087:
4083:
4079:
4075:
4071:
4067:
4062:
4058:
4054:
4050:
4047:
4024:
4020:
4016:
4012:
4008:
4005:
4001:
3997:
3993:
3989:
3985:
3981:
3977:
3973:
3970:
3939:
3936:
3932:
3928:
3924:
3903:
3900:
3887:
3864:
3861:
3858:
3855:
3852:
3849:
3844:
3840:
3836:
3833:
3830:
3827:
3824:
3821:
3816:
3812:
3808:
3805:
3782:
3762:
3742:
3722:
3698:
3693:
3689:
3685:
3682:
3662:
3657:
3653:
3649:
3646:
3626:
3623:
3620:
3615:
3611:
3607:
3602:
3598:
3594:
3591:
3571:
3566:
3562:
3558:
3555:
3552:
3549:
3546:
3543:
3538:
3534:
3530:
3527:
3504:
3499:
3495:
3491:
3488:
3485:
3482:
3479:
3476:
3471:
3467:
3463:
3460:
3457:
3454:
3451:
3448:
3443:
3439:
3435:
3432:
3423:by induction,
3412:
3409:
3406:
3401:
3397:
3393:
3388:
3384:
3380:
3377:
3374:
3371:
3366:
3362:
3358:
3355:
3352:
3349:
3346:
3343:
3338:
3334:
3330:
3327:
3304:
3301:
3298:
3293:
3289:
3285:
3280:
3276:
3272:
3269:
3266:
3263:
3260:
3257:
3252:
3248:
3244:
3241:
3238:
3235:
3232:
3229:
3224:
3220:
3216:
3213:
3190:
3170:
3150:
3130:
3110:
3090:
3068:
3064:
3041:
3037:
3016:
2992:
2988:
2983:
2962:
2955:
2951:
2946:
2942:
2939:
2919:
2914:
2910:
2906:
2899:
2895:
2890:
2886:
2883:
2861:
2857:
2833:
2828:
2824:
2820:
2817:
2814:
2811:
2808:
2805:
2800:
2796:
2792:
2789:
2766:
2746:
2743:
2740:
2737:
2732:
2728:
2707:
2704:
2699:
2695:
2674:
2671:
2668:
2665:
2660:
2656:
2635:
2613:
2609:
2588:
2568:
2546:
2542:
2521:
2501:
2481:
2461:
2441:
2421:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2354:
2351:
2331:
2323:
2303:
2298:
2295:
2290:
2287:
2284:
2281:
2278:
2254:
2234:
2226:
2199:
2191:
2179:
2176:
2159:
2139:
2115:
2095:
2075:
2055:
2035:
2015:
1995:
1980:
1977:
1960:
1957:
1954:
1934:
1914:
1894:
1874:
1854:
1834:
1814:
1794:
1773:
1753:
1745:
1725:
1705:
1685:
1665:
1645:
1642:
1639:
1636:
1633:
1630:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1533:
1530:
1527:
1507:
1487:
1467:
1447:
1427:
1407:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1337:
1334:
1330:
1326:
1322:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1258:
1234:
1214:
1211:
1208:
1182:
1179:
1176:
1172:
1169:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1120:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1051:
1031:
1028:
1008:
988:
968:
948:
928:
908:
905:
885:
865:
844:
840:
837:
834:
830:
825:
821:
818:
815:
812:
809:
806:
786:
766:
746:
726:
706:
703:
700:
697:
694:
673:
669:
666:
663:
659:
638:
618:
615:
612:
609:
606:
586:
566:
546:
523:
503:
483:
463:
443:
423:
403:
383:
363:
343:
323:
303:
300:
297:
294:
291:
271:
268:
265:
262:
259:
256:
253:
250:
247:
235:
232:
197:
177:
157:
137:
117:
97:
77:
57:
15:
13:
10:
9:
6:
4:
3:
2:
6445:
6434:
6431:
6429:
6426:
6425:
6423:
6413:
6410:
6409:
6405:
6391:
6387:
6381:
6378:
6370:
6364:
6362:
6358:
6350:
6344:
6342:
6338:
6333:
6327:
6325:
6323:
6321:
6319:
6317:
6313:
6302:
6301:www.boost.org
6298:
6292:
6289:
6283:
5365:
4618:
4616:
4608:
4606:
4584:
4576:
4573:
4565:
4557:
4549:
4538:
4515:
4509:
4481:
4473:
4470:
4464:
4456:
4435:
4405:
4380:
4377:
4357:
4337:
4317:
4297:
4277:
4257:
4234:
4231:
4228:
4222:
4202:
4182:
4162:
4142:
4133:
4111:
4103:
4100:
4095:
4085:
4077:
4069:
4056:
4045:
4036:
4014:
4006:
4003:
3995:
3987:
3979:
3968:
3960:
3955:
3953:
3937:
3934:
3926:
3913:
3909:
3901:
3899:
3885:
3875:
3859:
3853:
3850:
3842:
3838:
3831:
3828:
3822:
3819:
3814:
3810:
3803:
3794:
3780:
3760:
3740:
3720:
3710:
3691:
3687:
3680:
3655:
3651:
3644:
3621:
3618:
3613:
3609:
3605:
3600:
3596:
3589:
3564:
3560:
3553:
3550:
3544:
3541:
3536:
3532:
3525:
3515:
3497:
3493:
3486:
3483:
3477:
3474:
3469:
3465:
3458:
3455:
3449:
3446:
3441:
3437:
3430:
3407:
3404:
3399:
3395:
3391:
3386:
3382:
3375:
3372:
3364:
3360:
3353:
3350:
3344:
3341:
3336:
3332:
3325:
3315:
3299:
3296:
3291:
3287:
3283:
3278:
3274:
3267:
3264:
3258:
3255:
3250:
3246:
3239:
3236:
3230:
3227:
3222:
3218:
3211:
3202:
3188:
3168:
3148:
3128:
3108:
3088:
3066:
3062:
3039:
3035:
3014:
2990:
2986:
2981:
2953:
2949:
2944:
2937:
2912:
2908:
2904:
2897:
2893:
2888:
2881:
2859:
2855:
2844:
2826:
2822:
2815:
2812:
2806:
2803:
2798:
2794:
2787:
2778:
2764:
2741:
2735:
2730:
2726:
2705:
2702:
2697:
2693:
2669:
2663:
2658:
2654:
2633:
2611:
2607:
2586:
2566:
2544:
2540:
2519:
2499:
2492:is active if
2479:
2459:
2439:
2419:
2396:
2393:
2387:
2384:
2378:
2372:
2352:
2349:
2329:
2321:
2293:
2288:
2285:
2279:
2276:
2266:
2252:
2232:
2224:
2216:
2211:
2197:
2189:
2177:
2175:
2171:
2157:
2137:
2128:
2113:
2093:
2073:
2053:
2033:
2013:
1993:
1984:
1978:
1976:
1974:
1958:
1955:
1952:
1932:
1912:
1892:
1872:
1852:
1832:
1812:
1792:
1771:
1751:
1743:
1723:
1703:
1683:
1663:
1640:
1637:
1634:
1628:
1605:
1602:
1599:
1596:
1590:
1587:
1584:
1578:
1569:
1563:
1560:
1557:
1551:
1531:
1528:
1525:
1505:
1485:
1465:
1445:
1425:
1405:
1394:
1390:
1372:
1369:
1366:
1363:
1360:
1350:
1335:
1332:
1324:
1312:
1294:
1291:
1288:
1285:
1282:
1272:
1256:
1248:
1232:
1212:
1209:
1206:
1196:
1180:
1177:
1174:
1167:
1145:
1142:
1139:
1136:
1133:
1123:
1119:
1102:
1099:
1096:
1090:
1087:
1081:
1078:
1075:
1069:
1049:
1029:
1026:
1006:
986:
966:
946:
926:
906:
903:
883:
863:
842:
838:
835:
832:
828:
823:
816:
813:
807:
804:
784:
764:
744:
724:
701:
698:
695:
671:
667:
664:
661:
657:
636:
613:
610:
607:
584:
564:
544:
535:
521:
501:
481:
461:
441:
421:
401:
381:
361:
341:
321:
301:
298:
295:
292:
289:
266:
263:
260:
257:
254:
248:
245:
233:
231:
229:
225:
220:
216:
215:
209:
195:
175:
155:
135:
115:
95:
75:
55:
46:
42:
39:to solve the
38:
34:
30:
21:
6393:. Retrieved
6389:
6380:
6304:. Retrieved
6300:
6291:
5996:Stoer_Wagner
5364:
4676:globalMinCut
4612:
4609:Example code
4270:is added to
4134:
4037:
3958:
3956:
3951:
3911:
3908:running time
3905:
3877:
3796:
3713:Thus, since
3712:
3518:
3318:
3204:
2846:
2780:
2268:
2214:
2213:
2181:
2172:
2129:
2046:. Next, set
1985:
1982:
1971:phases, the
1736:, and a min
1438:is equal to
1397:
1392:
1388:
1348:
1310:
1270:
1246:
1194:
1121:
536:
237:
212:
210:
32:
29:graph theory
26:
5558:// Find s,t
5039:max_element
4215:, that is,
3673:but not to
1973:minimum cut
1805:separating
514:min-cut of
219:minimum cut
43:problem in
41:minimum cut
6422:Categories
6395:2021-11-17
6390:github.com
6306:2015-12-07
6284:References
5954:&&
5783:&&
5774:&&
5399:1000000000
3912:MinimumCut
1905:must have
1544:such that
1271:MinimumCut
45:undirected
4643:namespace
4577:
4474:
4104:
4007:
3935:−
3829:≤
3606:−
3551:≤
3484:≤
3456:≤
3392:−
3351:≤
3284:−
3161:added to
2813:≤
2736:∪
2703:⊆
2664:∪
2385:≥
2342:cut, and
2297:¯
1956:−
1603:∉
1597:∣
1529:∉
1210:≠
1171:←
808:∪
299:∈
6104:contract
5528:contract
4787:>>
4730:>>
4697:>>
4673:>>
4634:#include
3957:For the
3950:runs of
2245:-cut of
1621:, where
48:minimum
5342:INT_MIN
5015:INT_MIN
4742:INT_MAX
4330:not in
3181:before
3141:, with
3027:before
2685:, i.e.
2579:before
2215:Lemma 1
1979:Example
1225:add to
228:network
6272:mincut
6269:return
6182:return
6170:mincut
6152:mincut
6140:mincut
6050:mincut
6008:mincut
5984:mincut
5981:return
5879:mincut
5849:mincut
5846:return
5645:mincut
5612:sizeof
5594:memset
5582:sizeof
5564:memset
5510:sizeof
5492:memset
5480:sizeof
5462:memset
5351:return
5186:insert
4928:size_t
4904:vector
4778:vector
4772:vector
4721:vector
4688:vector
4682:vector
4664:vector
4035:time.
3582:since
2599:, and
1845:, the
1204:
557:and a
394:is in
31:, the
6372:(PDF)
6352:(PDF)
6212:<=
5924:<=
5744:<=
5678:<=
5606:false
5549:&
5537:&
5504:false
5387:const
5369:const
5210:begin
5078:begin
5051:begin
4640:using
3753:from
1311:while
1195:while
737:, or
35:is a
6260:edge
6254:edge
6245:edge
6143:>
6128:true
6077:<
5972:edge
5966:dist
5897:true
5885:maxc
5819:dist
5813:maxc
5792:maxc
5789:>
5786:dist
5711:maxc
5651:maxc
5588:dist
5570:dist
5486:edge
5468:edge
5453:init
5450:void
5435:bool
5429:dist
5423:edge
5375:maxn
5354:best
5306:<
5252:<
5225:());
5153:best
5141:best
5108:<
4979:<
4913:>
4907:<
4883:<
4826:<
4781:<
4775:<
4766:size
4748:{}};
4733:best
4724:<
4712:<
4709:pair
4691:<
4685:<
4667:<
4655:<
4652:pair
3906:The
3121:and
2930:and
2847:Let
2452:and
2269:Let
2106:and
1925:and
1825:and
1764:cut
1716:and
1676:and
1393:then
1333:>
979:and
939:and
876:and
757:and
238:Let
148:and
108:and
6239:bin
6191:for
6158:ans
6146:ans
6122:bin
6098:ans
6056:inf
6044:for
6038:ans
6005:int
5993:int
5960:vis
5951:bin
5903:for
5891:vis
5780:vis
5771:bin
5723:for
5657:for
5624:int
5621:));
5618:vis
5600:vis
5591:));
5546:int
5534:int
5525:int
5519:));
5516:bin
5498:bin
5489:));
5444:bin
5438:vis
5420:int
5405:int
5393:inf
5390:int
5381:550
5372:int
5336:mat
5330:mat
5324:mat
5288:int
5282:for
5276:mat
5270:mat
5234:int
5228:for
5222:end
5213:(),
5201:(),
5198:end
5177:});
5168:mat
5147:min
5132:mat
5090:int
5084:for
5081:();
5066:())
5063:end
5054:(),
4961:int
4955:for
4922:mat
4910:int
4865:int
4859:for
4808:int
4802:for
4784:int
4769:();
4760:mat
4751:int
4727:int
4715:int
4700:mat
4694:int
4670:int
4658:int
4646:std
4615:C++
4574:log
4471:log
4101:log
4004:log
1573:max
1247:end
1062:is
1042:to
629:of
577:in
374:or
214:cut
27:In
6424::
6388:.
6360:^
6340:^
6315:^
6299:.
6263:);
6257:+=
6230:if
6224:++
6173:==
6164:if
6134:if
6119:);
6089:++
5999:()
5969:+=
5942:if
5936:++
5840:-1
5837:==
5828:if
5762:if
5756:++
5717:-1
5705:-1
5690:++
5456:()
5318:++
5273:+=
5264:++
5216:co
5204:co
5192:co
5180:co
5174:co
5129:+=
5120:++
4997:++
4994:it
4988:ph
4976:it
4964:it
4895:++
4892:ph
4880:ph
4868:ph
4856:};
4844:co
4838:++
4799:);
4790:co
4625://
4605:.
4132:.
3898:.
1389:if
534:.
211:A
6398:.
6374:.
6354:.
6334:.
6309:.
6278:}
6275:;
6266:}
6251:(
6248:=
6242:)
6236:!
6233:(
6227:)
6221:j
6218:;
6215:n
6209:j
6206:;
6203:1
6200:=
6197:j
6194:(
6188:;
6185:0
6179:)
6176:0
6167:(
6161:;
6155:=
6149:)
6137:(
6131:;
6125:=
6116:t
6113:,
6110:s
6107:(
6101:=
6095:{
6092:)
6086:i
6083:;
6080:n
6074:i
6071:;
6068:1
6065:=
6062:i
6059:,
6053:=
6047:(
6041:;
6035:,
6032:t
6029:,
6026:s
6023:,
6020:j
6017:,
6014:i
6011:,
6002:{
5990:}
5987:;
5978:}
5975:;
5963:)
5957:!
5948:!
5945:(
5939:)
5933:j
5930:;
5927:n
5921:j
5918:;
5915:1
5912:=
5909:j
5906:(
5900:;
5894:=
5888:;
5882:=
5876:;
5873:k
5870:=
5867:t
5864:;
5861:t
5858:=
5855:s
5852:;
5843:)
5834:k
5831:(
5825:}
5822:;
5816:=
5810:;
5807:j
5804:=
5801:k
5798:{
5795:)
5777:!
5768:!
5765:(
5759:)
5753:j
5750:;
5747:n
5741:j
5738:;
5735:1
5732:=
5729:j
5726:(
5720:;
5714:=
5708:;
5702:=
5699:k
5696:{
5693:)
5687:i
5684:;
5681:n
5675:i
5672:;
5669:1
5666:=
5663:i
5660:(
5654:;
5648:,
5642:,
5639:k
5636:,
5633:j
5630:,
5627:i
5615:(
5609:,
5603:,
5597:(
5585:(
5579:,
5576:0
5573:,
5567:(
5561:{
5555:)
5552:t
5543:,
5540:s
5531:(
5522:}
5513:(
5507:,
5501:,
5495:(
5483:(
5477:,
5474:0
5471:,
5465:(
5459:{
5447:;
5441:,
5432:;
5426:,
5417:;
5414:r
5411:,
5408:n
5402:;
5396:=
5384:;
5378:=
5360:}
5357:;
5348:}
5345:;
5339:=
5333:;
5327:=
5321:)
5315:i
5312:;
5309:n
5303:i
5300:;
5297:0
5294:=
5291:i
5285:(
5279:;
5267:)
5261:i
5258:;
5255:n
5249:i
5246:;
5243:0
5240:=
5237:i
5231:(
5219:.
5207:.
5195:.
5189:(
5183:.
5171:,
5165:-
5162:w
5159:{
5156:,
5150:(
5144:=
5138:}
5135:;
5126:w
5123:)
5117:i
5114:;
5111:n
5105:i
5102:;
5099:0
5096:=
5093:i
5087:(
5075:.
5072:w
5069:-
5060:.
5057:w
5048:.
5045:w
5042:(
5036:=
5033:t
5030:,
5027:t
5024:=
5021:s
5018:;
5012:=
5009:w
5003:{
5000:)
4991:;
4985:-
4982:n
4973:;
4970:0
4967:=
4958:(
4952:;
4949:0
4946:=
4943:t
4940:,
4937:0
4934:=
4931:s
4925:;
4919:=
4916:w
4901:{
4898:)
4889:;
4886:n
4877:;
4874:1
4871:=
4862:(
4853:i
4850:{
4847:=
4841:)
4835:i
4832:;
4829:n
4823:i
4820:;
4817:0
4814:=
4811:i
4805:(
4796:n
4793:(
4763:.
4757:=
4754:n
4745:,
4739:{
4736:=
4718:,
4706:{
4703:)
4679:(
4661:,
4649:;
4593:)
4589:|
4585:V
4581:|
4570:|
4566:V
4562:|
4558:+
4554:|
4550:E
4546:|
4542:(
4539:O
4519:)
4516:1
4513:(
4510:O
4490:)
4486:|
4482:V
4478:|
4468:(
4465:O
4440:|
4436:E
4432:|
4410:|
4406:V
4402:|
4381:w
4378:v
4358:v
4338:A
4318:w
4298:v
4278:A
4258:v
4238:)
4235:v
4232:,
4229:A
4226:(
4223:w
4203:A
4183:V
4163:A
4143:A
4120:)
4116:|
4112:V
4108:|
4096:2
4091:|
4086:V
4082:|
4078:+
4074:|
4070:E
4066:|
4061:|
4057:V
4053:|
4049:(
4046:O
4023:)
4019:|
4015:V
4011:|
4000:|
3996:V
3992:|
3988:+
3984:|
3980:E
3976:|
3972:(
3969:O
3938:1
3931:|
3927:V
3923:|
3886:C
3863:)
3860:C
3857:(
3854:w
3851:=
3848:)
3843:t
3839:C
3835:(
3832:w
3826:)
3823:t
3820:,
3815:t
3811:A
3807:(
3804:w
3793::
3781:t
3761:t
3741:s
3721:t
3697:)
3692:v
3688:C
3684:(
3681:w
3661:)
3656:u
3652:C
3648:(
3645:w
3625:)
3622:u
3619:,
3614:v
3610:A
3601:u
3597:A
3593:(
3590:w
3570:)
3565:u
3561:C
3557:(
3554:w
3548:)
3545:u
3542:,
3537:u
3533:A
3529:(
3526:w
3503:)
3498:v
3494:C
3490:(
3487:w
3481:)
3478:v
3475:,
3470:v
3466:A
3462:(
3459:w
3453:)
3450:u
3447:,
3442:v
3438:A
3434:(
3431:w
3411:)
3408:u
3405:,
3400:v
3396:A
3387:u
3383:A
3379:(
3376:w
3373:+
3370:)
3365:v
3361:C
3357:(
3354:w
3348:)
3345:u
3342:,
3337:u
3333:A
3329:(
3326:w
3303:)
3300:u
3297:,
3292:v
3288:A
3279:u
3275:A
3271:(
3268:w
3265:+
3262:)
3259:u
3256:,
3251:v
3247:A
3243:(
3240:w
3237:=
3234:)
3231:u
3228:,
3223:u
3219:A
3215:(
3212:w
3201::
3189:u
3169:A
3149:v
3129:u
3109:v
3089:C
3067:0
3063:v
3040:0
3036:v
3015:A
2991:0
2987:v
2982:A
2961:)
2954:0
2950:v
2945:C
2941:(
2938:w
2918:)
2913:0
2909:v
2905:,
2898:0
2894:v
2889:A
2885:(
2882:w
2860:0
2856:v
2832:)
2827:v
2823:C
2819:(
2816:w
2810:)
2807:v
2804:,
2799:v
2795:A
2791:(
2788:w
2777:,
2765:v
2745:}
2742:v
2739:{
2731:v
2727:A
2706:C
2698:v
2694:C
2673:}
2670:v
2667:{
2659:v
2655:A
2634:C
2612:v
2608:C
2587:v
2567:A
2545:v
2541:A
2520:v
2500:v
2480:v
2460:t
2440:s
2420:a
2400:)
2397:P
2394:C
2391:(
2388:W
2382:)
2379:C
2376:(
2373:W
2353:P
2350:C
2330:t
2326:-
2322:s
2302:)
2294:X
2289:,
2286:X
2283:(
2280:=
2277:C
2265:.
2253:G
2233:t
2229:-
2225:s
2198:t
2194:-
2190:s
2158:A
2138:A
2114:t
2094:s
2074:A
2054:A
2034:A
2014:A
1994:G
1959:1
1953:n
1933:t
1913:s
1893:G
1873:G
1853:C
1833:t
1813:s
1793:G
1772:C
1752:t
1748:-
1744:s
1724:t
1704:s
1684:y
1664:A
1644:)
1641:y
1638:,
1635:A
1632:(
1629:w
1609:}
1606:A
1600:y
1594:)
1591:y
1588:,
1585:A
1582:(
1579:w
1576:{
1570:=
1567:)
1564:z
1561:,
1558:A
1555:(
1552:w
1532:A
1526:z
1506:A
1486:A
1466:A
1446:V
1426:A
1406:A
1376:)
1373:a
1370:,
1367:w
1364:,
1361:G
1358:(
1336:1
1329:|
1325:V
1321:|
1298:)
1295:a
1292:,
1289:w
1286:,
1283:G
1280:(
1257:G
1233:A
1213:V
1207:A
1181:}
1178:a
1175:{
1168:A
1149:)
1146:a
1143:,
1140:w
1137:,
1134:G
1131:(
1106:)
1103:v
1100:,
1097:t
1094:(
1091:w
1088:+
1085:)
1082:v
1079:,
1076:s
1073:(
1070:w
1050:v
1030:t
1027:s
1007:v
987:t
967:s
947:t
927:s
907:t
904:s
884:t
864:s
843:}
839:t
836:,
833:s
829:{
824:/
820:}
817:t
814:s
811:{
805:G
785:G
765:t
745:s
725:G
705:)
702:T
699:,
696:S
693:(
672:}
668:t
665:,
662:s
658:{
637:G
617:)
614:T
611:,
608:S
605:(
585:V
565:t
545:s
522:G
502:t
494:-
482:s
462:t
454:-
442:s
422:G
402:S
382:t
362:s
342:t
334:-
322:s
302:V
296:t
293:,
290:s
270:)
267:w
264:,
261:E
258:,
255:V
252:(
249:=
246:G
196:t
188:-
176:s
156:t
136:s
116:t
96:s
76:t
68:-
56:s
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
