[알고리즘] 단절선(bridge or cut edge)

[알고리즘] 단절선(bridge or cut edge)

#include < iostream >

#include < string >

#include < algorithm >

#include < queue >

#include < vector >

#include < stack >

#include < utility >

#include < climits >

#include < deque >

using namespace std ;

vector < int > adj[ 100001 ];

int visited[ 100001 ];

vector < pair < int , int > > cutEdge;

int v, e;

int num = 1 ;

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

int dfs( int A, int parent) {

visited[A] = num + + ;

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

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

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

if (visited[next]) {

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

continue ;

}

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

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

cutEdge. push_back ({ min(A, next), max(A, next) }); //단절선

}

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

}

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 );

}

sort(cutEdge. begin (), cutEdge. end ());

cout < < cutEdge. size () < < '

' ;

for ( auto e : cutEdge) {

cout < < e.first < < " " < < e.second < < '

' ;

}

return 0 ;

}

from http://seokjin2.tistory.com/89 by ccl(A) rewrite - 2021-12-19 18:01:41