[JAVA] 백준 q14675 - 단절점과 단절선

14675번: 단절점과 단절선

---

> 의식의 흐름

간선은 끊으면 어떤 경우여도 그래프가 2개로 나뉘니까 yes일거고 정점은 다른 정점 한 개랑 연결된 애만 아니면 되겠지..?

 

> 풀이 과정

1. 각 정점에 대해 연결된 정점 번호를 담을 ArrayList 생성

ArrayList<ArrayList<Integer>> links = new ArrayList<>();

for(int i=0;i<=N;i++){
   links.add(new ArrayList<Integer>());
}

2. 입력으로 주어지는 간선 정보를 바탕으로 1번에서 생성한 ArrayList를 채운다.
3-1. 질의 유형이 `1`인 경우, 단절점인지 판단한다.

• k번 정점과 연결된 정점이 1개이면, k번 정점이 제거되어도 그래프가 2개로 나눠지지 않으므로 "no"를 출력한다.
• k번 정점과 연결된 정점이 2개 이상이면, k번 정점이 제거되었을 때 그래프가 2개 이상으로 나눠지므로 "yes"를 출력한다.

3-2. 질의 유형이 `2`인 경우, 단절선인지 판단한다.
이때, 간선을 끊으면 항상 그래프가 2개 이상으로 나눠지므로 무조건 "yes"를 출력한다.
4. q개의 질의에 대해 3번 과정을 반복한다.

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static int N, q;
    public static ArrayList<ArrayList<Integer>> links = new ArrayList<>();

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

        N = Integer.parseInt(br.readLine()); // 정점의 개수
        for(int i=0;i<=N;i++){
            links.add(new ArrayList<Integer>());
        }

        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());

            links.get(a).add(b);
            links.get(b).add(a);
        }

        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()); // k번째 정점/간선

            switch (t){
                case 1: // 단절점인지
                    if(links.get(k).size()==1){
                        // 연결된 정점 개수가 1개인 경우
                        bw.write("no\n");
                    }
                    else{
                        bw.write("yes\n");
                    }
                    break;
                case 2: // 단절선인지
                    // 간선을 끊으면 무조건 2개 이상의 그래프로 나뉨
                    bw.write("yes\n");
                    break;
            }
        }

        bw.flush();

        br.close();
        bw.close();
    }
}