링크

14675 단절점과 단절선

문제

풀이

생각해보면 간단하게 풀 수 있는 문제이다.

일단 단절선을 생각해봤을때 어디를 잘라도 그래프가 2개로 나눠진다. 그래서 무조건 yes를 출력했다

단절점이 문제이다.
단절점은 만약 루트노드랑 연결된 노드가 1개이거나 리프노드들이면 잘라도 그래프가 1개이다.
즉 노드가 연결된 정점이 2개 이상이라면 잘랐을때 2개의 그래프로 나눠지는 것을 찾았다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.sql.Array;
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());

        List<Integer>[] list = new ArrayList[n+1];

        for(int i=0;i<list.length;i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<n-1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        n = Integer.parseInt(br.readLine());

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

            if(t == 2) sb.append("yes");
            else{
                if(list[k].size() >= 2) sb.append("yes");
                else sb.append("no");
            }

            sb.append("\n");
        }

        System.out.println(sb.toString());





    }

}