Разбор добавил Джафар Исхоков

Необязательно использовать обход графа.
Достаточно при считывании данных для каждой вершины хранить число, сколько она встретилась раз. Если 
более одного, значит она соединяет какие-то вершины и является важной.