[JAVA] 백준 14675번 - 단절점과 단절선

 

풀이방법

- 이번 문제에서 핵심은 단절점과 단절선을 트리에서 구한다는 점이다.
트리는 사이클이 존재하지 않고 모든 정점이 연결되어있다고 명시되어있다.

이를 이용하면 첫번째로 어떤 간선을 제거하더라도 해당 간선이 포함된 그래프가 2개

이상으로 나오게 된다. 따라서 질의 k가 2일때는 반드시 yes를 출력하면 된다.

 

- 두번째로 어떤 정점을 제거했을때 해당 정점이 포함된 그래프가 2개 이상으로 나오지 않는 경우는 해당 정점이

'루트노드'이거나 '단말노드'일 경우이다. 루트노드나 단말노드가 아닌 단절점인 노드는 트리의 정점 개수 N만큼 반복하여 연결정보를 입력 받을 때 2번이상씩 나오게 되어있으므로 전체 연결정보를 배열에 담은 뒤 인덱스 값이 '1'인
노드가 단절점이 아닌 노드라고 보면 된다. 따라서 질의 k가 1일때 array[t] == 1 이면 no를, array[t] > 1 라면 yes를

출력하면된다.

 

Code

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] array = new int[100000];
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<n-1; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            array[a] = array[a] + 1;
            array[b] = array[b] + 1;
        }

        int q = Integer.parseInt(br.readLine());
        for(int i = 0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            if (k == 1){
                if(array[t] > 1){
                    sb.append("yes").append("\n");
                }else if(array[t] == 1){
                    sb.append("no").append("\n");
                }
            }else
                sb.append("yes").append("\n");
        }
        System.out.println(sb);
    }
}