[백준] 단절점과 단절선 - 실버1, 트리(Tree)

https://www.acmicpc.net/problem/14675

14675번: 단절점과 단절선

 

기억해야할점입니다.

 

첫번째, 트리에서 단절점과 단절선 구하는방법
  트리(Tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프입니다.
단절점 구하는 방법 : 삭제할려는 노드가 끝 정점이 아니라면 단절점이 됩니다. 
  즉, 연결된 간선개수가 2개 이상이라면 단절점이 됩니다. 
단절선 구하는 방법 : 모든 간선이 단절선이다. (사이클이 존재하지 않기에 모든 간선이 단절선입니다.)

t가 2라면 모든 간선은 단절선이므로 바로 "yes"를 출력합니다.
t가 1이면 연결된 간선의 개수가 2 이상이라면 단절점입니다. 1이면 끝점이므로 단절점이 아닙니다.

 

 

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		
		for(int i=0;i<=N;i++) {
			graph.add(new ArrayList<Node>());
		}
		
		for(int i=1;i<N;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			graph.get(start).add(new Node(end));
			graph.get(end).add(new Node(start));
		}
		
		int q = sc.nextInt();
		for(int i=0;i<q;i++) {
			int t = sc.nextInt();
			int k = sc.nextInt();
			if(t == 2) {
				System.out.println("yes");
			}
			if(t == 1) {
				if(graph.get(k).size() >= 2) {
					System.out.println("yes");
				}else {
					System.out.println("no");
				}
			}
		}
		
		
		
	}
	static class Node{
		int index;
		public Node(int index) {
			this.index = index;
		}
	}
}