[알고리즘] 단절점(Articulation Points or Cut Vertices)

[알고리즘] 단절점(Articulation Points or Cut Vertices)

#include < iostream >

#include < string >

#include < algorithm >

#include < queue >

#include < vector >

#include < stack >

#include < utility >

#include < climits >

#include < deque >

using namespace std ;

int v, e;

vector < int > adj[ 10001 ];

int visited[ 10001 ];

bool cutVertex[ 10001 ];

int num = 1 ;

/*정점 A가 우회로를 통해서 갈 수 있는 가장 빠른 정점을 리턴*/

int dfs( int A, int parent, bool isRoot) {

visited[A] = num + + ;

int child = 0 ;

int ret = visited[A]; //처음엔 자기 자신이 최상위 노드

for ( auto & next : adj[A]) {

if (next = = parent) continue ; //부모를 제외

if (visited[next]) {

ret = min(ret, visited[next]); // 우회로 갱신

continue ;

}

child + + ;

int low = dfs(next, A, false );// 자식 노드가 우회로를 통해서 갈 수 있는 가장 빠른 정점

if ( ! isRoot & & low > = visited[A]) { //자식 노드가 정점 A보다 위에 있는 선조로 갈 수 없으면

cutVertex[A] = true ; // 단절점

}

ret = min(ret, low); //정점 A가 갈 수 있는 선조 업데이트

}

if (isRoot) {

cutVertex[A] = child > = 2 ? true : false ;

}

return ret;

}

int main( void ) {

ios::sync_with_stdio( false );

cin .tie(nullptr);

cin > > v > > e;

for ( int i = 0 ; i < e; i + + ) {

int a, b;

cin > > a > > b;

adj[a]. push_back (b);

adj[b]. push_back (a);

}

for ( int i = 1 ; i < = v; i + + ) {

if ( ! visited[i]) {

dfs(i, 0 , true );

}

}

int cnt = 0 ;

for ( int i = 1 ; i < = v; i + + ) {

if (cutVertex[i]) cnt + + ;

}

cout < < cnt < < '

' ;

for ( int i = 1 ; i < = v; i + + ) {

if (cutVertex[i]) cout < < i < < ' ' ;

}

return 0 ;

}

from http://seokjin2.tistory.com/87 by ccl(A) rewrite - 2021-12-19 16:01:06