정점 제거로 인한 최대 고립
플래티넘 IV의견: 0
정점 \(N\)개, 간선 \(M\)개의 연결된 무방향 단순 그래프가 주어진다. 정점 하나(와 인접 간선)를 제거할 수 있다.
어떤 정점 하나를 제거하면 남은 \(N-1\)개의 정점이 여러 연결 요소로 쪼개질 수 있다. 이때 가장 큰 연결 요소에 속하지 않는 정점의 수(즉, \((N-1) -\) (가장 큰 남은 요소의 크기))를 그 정점의 '고립 수'라 하자.
모든 정점에 대해 고립 수를 계산했을 때의 최댓값을 출력하라.
\(1 \le N \le 100{,}000\)
\(N-1 \le M \le 200{,}000\) (연결 그래프)
\(1 \le u, v \le N\), \(u \ne v\), 단순 그래프
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 간선 \(u\ v\). 그래프는 연결되어 있다.
고립 수의 최댓값을 출력한다.
5 4
1 2
2 3
3 4
4 5
2경로 1-2-3-4-5. 정점 2를 지우면 {1}과 {3,4,5}로 갈라져 가장 큰 요소(3개)에 속하지 않는 정점은 1개. 정점 3을 지우면 {1,2},{4,5}로 최대 요소 2개, 고립 수 2. 최댓값은 가운데에서 2.
7 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
2두 삼각형이 정점 3-4 다리로 연결. 다리 끝 정점을 지우면 한쪽 삼각형이 떨어져 나가 고립 수가 커진다. 정답 3.
riseoj 작성
출처 Original
평가 및 의견
정점 제거로 인한 최대 고립
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
정점 제거로 인한 최대 고립