Один алгоритм комбинаторной генерации

[arseny30]

Ух. Формализма и правда хватает :)
Попробую резюмировать.

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

[krasko]

Ну, либо набор деревьев.

Да, всё так, причём важно, что если все описанные функции и отношения удовлетворяют перечисленным требованиям, то в графе каждый непомеченный объект встречается один раз (собственно, для того, чтобы имелась возможность это доказать, и нужен этот формализм).