Да, красятся только базы, но что такое база? Это сжатый номер вершины. Ну здесь прямо напрашивается аналогия с DSU: мы красим не сам элемент, а всё множество целиком, для чего надо покрасить только представителя этого множества, а потом при проверке "покрашенности" смотреть всегда только на представителя (в нашем случае всегда пишется "if (blossom[base[i]])").

База base[v] на момент входа в функцию - это пока не база обнаруженного цветка, это сжатый номер вершины в DSU. Задача этой функции - в том, чтобы пройтись от текущей вершины до корня обнаруженного цветка, и для каждой нечётной вершины проставить предка p[]. Этот процесс лучше по бумажке понять (в статью бы тоже было бы круто вставить картинку, но у меня большая лень на картинки, как можно заметить по всему сайту :))) ). Ещё раз, суть в том, что обход в ширину проставляет p[] только для вторых концов рёбер паросочетания; функция же mark_path проставляет p[] для первых концов паросочетания, но в обратную сторону. Т.е. если предки, проставленные обходом в ширину, ведут "вверх" по дереву обхода, то предки, доставленные mark_path'ом, ведут обратно "вниз".

Это и правда очень хитрый момент алгоритма, самый вынос мозга :) Такая хрень с предками нужна, чтобы по предкам всегда можно было дойти до корня цветка, встав в любую точку цветка. Ведь обход в ширину даёт информацию о предках только для чётных вершин (вторых концов рёбер парсоча); предки же из нечётных вершин должны вести по циклу в противоположную сторону, иначе мы из нечётной вершины ну никак не придём чередующимся путём в корень цветка.

Вот :) Несколько сумбурно, но может, чуть лучше, чем в статье написано.