Изменения

==Алгоритм вырезания соцветий==

Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей четно. Также для каждой вершины, расстояние до которой нечетно, в массиве предков <tex>p[]</tex> необходимо хранить ее предка {{---}} четную вершину. Заметим, что если в процессе обхода в ширину мы из текущей вершины <tex>v</tex> приходим в такую вершину <tex>u</tex>, являющуюся корнем или принадлежащую паросочетанию и дереву путей, то обе эти вершины принадлежат некоторому цветку. Действительно, при выполнении этих условий эти вершины являются чётными вершинами, следовательно расстояние от них до их наименьшего общего предка имеет одну чётность. Найдем наименьшего общего предка <tex>lca(u,v)</tex> вершин <tex>u</tex>, <tex>v</tex>, который является базой цветка. Для нахождения самого цикла необходимо пройтись от вершин <tex>u</tex>, <tex>v</tex> до базы цветка. В явном виде цветок сжимать не будем, просто положим в очередь обхода в ширину все вершины, принадлежащие цветку. Также для всех четных вершин (за исключением базы) назначим предком соседнюю вершину в цикле, а для вершин <tex>u</tex> и <tex>v</tex> назначим предками друг друга. Это позволит корректно восстановить цветок, в случае, когда при восстановление увеличивающего пути, мы зайдем в нечетную вершину цикла.