R00391
단절선
플래티넘 IV레이팅
의견: 0
설명
정점 \(N\)개, 간선 \(M\)개의 무방향 그래프가 주어진다(단순 그래프). 연결이라는 보장은 없다.
단절선(bridge)의 개수를 출력하라. 단절선이란, 그 간선 하나를 제거했을 때 연결 요소 개수가 증가하는 간선이다.
제약
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le u, v \le N\), \(u \ne v\), 단순 그래프
입력 형식
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 간선 \(u\ v\) (\(1 \le u, v \le N\), \(u \ne v\)).
출력 형식
단절선의 개수를 출력한다.
예제 1
입력
5 4
1 2
2 3
3 4
4 5
출력
4설명
경로 1-2-3-4-5의 모든 간선은 제거 시 그래프를 끊으므로 단절선 → 4개.
예제 2
입력
4 4
1 2
2 3
3 1
2 4
출력
1설명
삼각형의 세 간선은 단절선이 아니고, 2-4 간선만 단절선 → 1개.
플래티넘 III문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
단절선
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
단절선
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기