На emaxx представлен алгоритм поиска наибольшего паросочетания в произвольном графе ( https://e-maxx.ru/algo/matching_edmonds). Но ball_of_wool придумал такой алгоритм: https://pastebin.com/w8Z9SbEN. В этом алгоритме, в начале нужно разделить граф на компоненты связности, теперь для каждой компоненты, n раз пытаемся построить максимальное паросочетание, при помощи алгоритма куна, который запускается также n раз и из всех вариантов берем лучший. Кто-то может найти тест, на котором этот алгоритм не работает?