[백준 14675] 단절점과 단절선 (JAVA)

백준 14675번 문제 - 단절점과 단절선

14675번: 단절점과 단절선

---

문제 분석

 

• 트리에서 해당 점이 단절점인지, 해당 선이 단절선인지 유무를 출력한다.
  • 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우
  • 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우

 

---

해결 키 포인트

 

• 각 정점에 연결된 정점 정보를 ArrayList로 제작한다.
• 질문에 대한 답을 출력한다.
  • 단절점인가(1 k) : 정점(k)이 연결된 정점의 개수가 2보다 크거나 같으면 yes, 아니면 no
  • 단절선인가(2 k) : 문제 조건이 사이클이 존재하지 않고 모든 정점이 연결된 트리이므로 간선은 무조건적으로 단절선으로 yes
•  

 

---

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 각 정점에 연결되 있는 점 리스트
        ArrayList<Integer> [] lists = new ArrayList [N];
        for(int i=0;i<N;i++) {
            lists[i] = new ArrayList<>();
        }

        // 간선 입력
        for(int i=0;i<N-1;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            lists[a].add(b);
            lists[b].add(a);
        }

        // 질문 개수 Q 입력
        int Q = Integer.parseInt(br.readLine());

        // 질문 답변
        for(int i=0;i<Q;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int t = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken())-1;

            // k가 단절점인지 체크
            if(t == 1) {
                // 해당 점이 2개 이상과 연결되 있는 경우, 단절점 O
                if(lists[k].size() >= 2){
                    bw.write("yes\n");
                // 아닌 경우, 단절점 X
                }else {
                    bw.write("no\n");
                }
            }
            // k번째 간선이 단절선인지 체크
            else {
                // 현재 문제 조건이 트리인 경우이므로, 모든 간선이 단절선
                bw.write("yes\n");
            }
        }
        bw.flush();
        bw.close();
    }
}