[BOJ] 백준 11400번 : 단절선 (JAVA)

문제

그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

 

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

 

 

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다.

 

다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

 

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

 

그래프의 정점은 1부터 V까지 자연수이다.

 

 

출력

첫째 줄에 단절선의 개수 K를 출력한다.

 

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

 

 

풀이

DFS를 응용하여 풀 수 있는 문제였습니다.

 

 

이 문제는 단절점과 유사한 문제이므로 아직 단절점의 개념을 모르시는 분은 이곳을 클릭하여 포스팅을 꼭 정독하시길 바랍니다.

 

단절점은 특정 정점을 지우게 되면 연결 그래프가 2개로 늘어나는 점을 말하는데, 단절선은 이와 유사하게 특정 간선을 지우게 되면 연결 그래프가 2개로 늘어나는 선을 말합니다.

 

따라서, 단절점에서 그랬던 것처럼 특정 정점의 자식 정점의 방문 순서를 파악해야합니다.

 

이때, 주의할 점이 단절선을 판단할 때는 특정 정점이 자식 정점을 방문하기 위한 간선은 제외해야 합니다.

 

즉, root와 child 간의 간선은 고려하지 않고, 자식 정점의 방문 순서 중 가장 작은 자식 정점의 방문 순서를 구한 뒤, (root의 방문 순서) < (자식 정점의 방문 순서 중 가장 작은 자식 정점의 방문 순서) 를 만족한다면 root와 child  간의 간선은 모두 단절선이 되는 것입니다.

 

마지막으로, 출력할 때 x를 기준으로 오름차순 정렬하되, x가 같다면 y를 기준으로 오름차순 정렬하는 것만 주의해 주시면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.