6102 : 브리지 탐색 — 단절선 찾기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프에서 특정 간선을 제거했을 때, 그래프가 두 개 이상으로 분리되게(연결 컴포넌트의 수가 증가하게) 하는 간선을 단절선(Bridge) 또는 브리지라고 합니다.
DFS 스패닝 트리를 탐색하여 모든 브리지를 찾아 출력하는 프로그램을 작성하십시오.
출력 정렬 기준:
1. 각 간선은
2. 간선들 간에는
DFS 스패닝 트리를 탐색하여 모든 브리지를 찾아 출력하는 프로그램을 작성하십시오.
출력 정렬 기준:
1. 각 간선은
u v 형태로 출력하며 항상 u < v를 만족해야 합니다.2. 간선들 간에는
u를 기준으로 오름차순, u가 같다면 v를 기준으로 오름차순 정렬하여 한 줄에 하나씩 출력합니다.입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (1 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
출력 설명
첫째 줄에 브리지의 개수 K를 출력합니다.
둘째 줄부터 K개의 줄에 걸쳐 정렬 기준에 맞춰 각 브리지를 이루는 두 노드 번호를 출력합니다.
둘째 줄부터 K개의 줄에 걸쳐 정렬 기준에 맞춰 각 브리지를 이루는 두 노드 번호를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
2 3
3 4
4 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
1 2도움
간선 u-v (u가 부모)가 브리지가 되기 위한 조건은 v의 서브트리에서 u나 u의 조상으로 가는 역방향 간선이 단 하나도 없어야 합니다. 즉
low[v] > dfsn 여부를 검사하면 됩니다.