백준 14675 [자바] java 단절점과 단절선

문제 링크: https://www.acmicpc.net/problem/14675

14675번: 단절점과 단절선

 

▶문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

• 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
• 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다.

이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

• 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프

트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오.

---

▶입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정보 a, b가 주어진다. 이는 a정점과 b정점이 연결되어 있다는 뜻이며, 입력으로 주어지는 정보는 트리임이 보장된다. (1 ≤ a, b ≤ N)

다음 줄에는 질의의 개수 q가 주어진다. (1 ≤ q ≤ 100,000) 다음 q줄에는 질의 t k가 주어진다. (1 ≤ t ≤ 2) t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다. t가 1일 때는 (1 ≤ k ≤ n)이며, t가 2일 때는 (1 ≤ k ≤ n - 1)이다.

---

▶출력

프로그램의 출력은 표준 출력으로 한다. q줄에 대하여 해당 질의에 대한 답을 한다. 각각은 개행으로 구분하며, 질의가 맞다면 ‘yes’를, 질의가 틀리면 ‘no’를 출력한다.

---

▶해설

 

1. 단절선 

->사이클이 없는 트리이므로 어떠한 선을 선택해도 단절선이 되므로 항상 yes를 출력해주면된다.

2. 단절점

-> 양방향으로 그래프를 연결해주며, 선택된 단절점이 연결된 정점의 갯수가 2 개보다 크다면 단절점이며, 작으면 단절점이 아니다. List<>[] graph 리스트 배열을 사용하여 그래프를 완성했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;
 
 
class path {
    int start;
    int end;
 
    public path(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
 
public class Main {
 
 
    static int n, m;
    static List<Integer>[] graph;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
 
        graph = new ArrayList[n + 1];
 
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < n - 1; i++) {
            String[] s1 = br.readLine().split(" ");
            int start = Integer.parseInt(s1[0]);
            int end = Integer.parseInt(s1[1]);
            graph[start].add(end);
            graph[end].add(start);
 
        }
        int count = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < count; i++) {
            String[] s1 = br.readLine().split(" ");
            int type = Integer.parseInt(s1[0]);
            int num = Integer.parseInt(s1[1]);
            if (type == 1) {
                removeDot(num);
            } else {
                System.out.println("yes");
            }
        }
    }
 
    public static void removeDot(int num) {
        if (graph[num].size() >= 2) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
}