Алгоритм точки сочленения Тарьяна на сильно связанном графе

Question

Я изучаю Tarjan's articulation points finding algorithm, и он говорит, что корневой узел является точкой сочленения, если у него больше 1 ребенка. Но если граф сильно связан, корневой узел не должен быть точкой артикуляции, даже если он имеет более одного ребенка. Может кто-нибудь объяснить?

Answer 1

Если граф сильно связан, то его корень никогда не будет иметь 2 ребенка. Помните, мы говорим о дереве DFS здесь. Следовательно, в сильно связанном графе, корень DFS-дерева будет иметь только один ребенок, и это точно. Попробуйте его.