R00390
단절점
플래티넘 IV레이팅
의견: 0
설명
정점 \(N\)개, 간선 \(M\)개의 무방향 그래프가 주어진다(단순 그래프, 자기 간선·다중 간선 없음). 그래프가 연결이라는 보장은 없다.
단절점(articulation point)의 개수를 출력하라. 단절점이란, 그 정점과 그에 인접한 간선들을 모두 제거했을 때 그래프의 연결 요소 개수가 증가하는 정점이다.
제약
\(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
출력
3설명
경로 1-2-3-4-5. 양 끝(1,5)을 제외한 가운데 정점 2,3,4가 단절점 → 3개.
예제 2
입력
4 4
1 2
2 3
3 1
2 4
출력
1설명
삼각형 1-2-3에 4가 2에 매달림. 2를 지우면 4가 분리되므로 2만 단절점 → 1개.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
단절점
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
단절점
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기