Найти все вершины неориентированного графа

Задача. Дан неориентированный граф. Для каждой вершины указано число соседей и массив номеров соседей, как в предыдущей задаче. Составить алгоритм, который по заданному i печатает все вершины связной компоненты i по одному разу (и только их). Число действий не должно превосходить C*(общее число вершин и ребер в связной компоненте).
Решение. Программа в процессе работы будет "закрашивать" некоторые вершины графа. Незакрашенной частью графа будем называть то, что останется, если выбросить все закрашенные вершины и ведущие в них ребра. Процедура add(i) закрашивает связную компоненту i в незакрашенном графе (и не делает ничего, если вершина i уже закрашена).

procedure add (i:1..n);
 begin
 | if вершина i закрашена then begin
 | | ничего делать не надо
 | end else begin
 | | закрасить i (напечатать и пометить как закрашенную)
 | | для всех j, соседних с i
 | | | add(j);
 | | end;
 | end;
 end;

Докажем, что эта процедура действует правильно (в предположении, что рекурсивные вызовы работают правильно). В самом деле, ничего, кроме связной компоненты не закрашенного графа, она закрасить не может. Проверим, что вся она будет закрашена. Пусть k - вершина, доступная из вершины i по пути i-j-...-k, проходящему только по не закрашенным вершинам. Будем рассматривать только пути, не возвращающиеся снова в i. Из всех таких путей выберем путь с наименьшим j (в порядке просмотра соседей в цикле в процедуре). Тогда при рассмотрении предыдущих соседей ни одна из вершин j-...-k не будет закрашена (иначе j не было бы минимальным) и потому k окажется в связной компоненте не закрашенного графа к моменту вызова add(j). Что и требовалось. Чтобы установить конечность глубины рекурсии, заметим, что на каждом уровне рекурсии число не закрашенных вершин уменьшается хотя бы на 1.

Оценим число действий. Каждая вершина закрашивается не более одного раза - при первым вызове add(i) с данным i. Все последующие вызовы происходят при закрашивании соседей - количество таких вызовов не больше числа соседей - и сводятся к проверке того, что вершина i уже закрашена. Первый же вызов состоит в просмотре всех соседей и рекурсивных вызовах add(j) для всех них. Таким образом, общее число действий, связанных с вершиной i, не превосходит константы, умноженной на число ее соседей. Отсюда и вытекает требуемая оценка.