백준 14675번: 단절점과 단절선

문제 설명

주어진 트리의 노드 혹은 간선을 하나 제거했을 때 그래프가 둘로 나뉘는지를 판단하면 됩니다.

접근법

• N과 q의 숫자가 높아 직접 하나의 값을 자르고 트리가 2개로 나뉘는지 판단하면 안된다고 생각했습니다.

• 문제의 핵심은 트리의 정의입니다.

  • 사이클이 존재하지 않는다는 조건 덕분에 간선을 제거하면 무조건 두개의 트리가 생성됩니다.
    사이클이 존재하면 아래와 같은 경우에 체크된 간선을 제거해도 하나의 여전히 하나의 트리입니다.
    

• 하나의 간선을 가지는 노드를 제거하는 경우에는 트리가 여전히 하나로 유지됩니다. 반면 둘 이상의 간선을 가지는 노드를 제거하는 경우에는 반드시 트리가 둘로 나뉘게 됩니다.

정답

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

public class Main {
	public static void main(String[] args) throws IOException {	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[] v = new int[N+1];
		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());
			v[a]++;
			v[b]++;
		}
		
		int q = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			if(t == 1) {
				if(v[k] >= 2) {
					sb.append("yes\n");
				}else {
					sb.append("no\n");
				}
			}else if(t == 2) {
				sb.append("yes\n");
			}
		}
		System.out.println(sb.toString());
		
 	}
	
	
}