14675
-
[백준]14675: 단절점과 단절선 - JAVA문제풀이/백준 2021. 6. 11. 10:46
[백준]14675: 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 풀이 이 문제 트리의 성질을 잘 알고있다면 탐색 알고리즘을 사용하지 않고도 풀 수 있는 문제이다. 이 문제를 푸는데 필요한 트리의 성질은 다음과 같다. 트리는 사이클이 없고, 모든 정점이 연결되어 있다. (문제에 나와있다.) N개의 정점이 있을때 N-1개의 간선을 가진다. 입력 받은 정보는 현재 '트리'인 상태이며, 해당 트리가 두 부분으로 나눠지는지 확인하면 된다. 우선, t에 2가 입력되었을 때를 ..