목록단절선찾기 (1)

민규의 흔적

[알고리즘] 단절선(브릿지) [백준 11400번 - 단절선]

2023년 5월 13일문제 링크 : 11400번 - 단절선문제 그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.입력첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는..
알고리즘 2023. 5. 13. 13:33
이전 Prev 1 Next 다음