У меня было задание по лаб. раб. : 
Вас пригласили оптимизировать глобальную сеть фирмы Microsoft, для этого вам необходимо разделить всю сеть на подсети. Подсети можно отделить, если все связи между ними проходят через один компьютер, причем этот компьютер относится к обеим подсетям. Первоначальная сеть представлена в виде графа 

Так вот, задачу я решил таким образом: граф был задан матрицей смежности, я выбирал каждую вершину, удалял, делал обход в глубину, если граф после этого содержал все вершины, then переходил к следующей вершине; else  запоминал эту вершину как "хорошую", и переходил к след-й....   
Преподаватель, признал задачу выполненной, но не рационально, и настойчиво предложил поискать мне другие варианты алгоритмов этой задачи...  

cout<<"Помогите чем, кто может "  

Вообще, надо просто находить точки раздела графа...
Кормен, Лейзерсон, Ривест "Алгоритмы: построение и анализ", первое издание(с осликом на обложке). Страница 462, упр 23-2.