Давайте запустим два указателя по юношам только с Куном. Можно пересчитывать текущее паросочетание, добавляя или удаляя одну вершину. Что происходит если добавить вершину, тогда попробуем увеличить паросочетание из нее, если это получилось, тогда размер паросочетания увеличится на 1, иначе останется таким же. Если нужно удалить вершину, тогда она либо входит в паросочетание, либо нет, если нет, то можно смело ее удалять, это никак не повлияет на текущее паросочетание, иначе, освободится вершина в другой доли, которая входила вместе с удаляемой вершиной в паросочетание, тогда нужно попробовать улучшить паросочетание для той вершины которая входила с удаляемой в другой доли, если это получилось, значит, размер паросочетания остается таким же, иначе уменьшается на 1. Для простоты можно хранить метки насыщенности для двух долей, вместо одной. Теперь когда мы умеем добавлять/удалять вершину в паросочетание за 1 поиск в глубину, то мы можем запустить два указателя по юношам, и в зависимости от того равно ли паросочетание M, сдвигать правую или левую границу, на каждом шаге сдвигается либо левая, либо правая граница, таких сдвигов будет не более 2*N, на каждый сдвиг в худшем случае нужен поиск в глубину за O(N+M+K), но за счет маленькой константы это очень быстрый O(N(N+M+K)). Вот код который получает АС(Кун+2 указателя): Спасибо Burunduk1! http://pastebin.com/XPFRF7AY