백준 - 단절점과 단절선

문제 설명

트리가 주어졌을 떄, 해당 간선 또는 정점을 제거하여 두개 이상의 그래프로 나뉘어 질 수 있다면 “yes” 아니면 “no”를 출력하는 문제이다.

풀이

‘간선’ 이라 함은 두 정점을 연결하는 요소로서 어느 간선을 제거하던 두 그래프의 단위로 무조건 나눌 수 있다는 것이다.

어느 한 정점을 제거했을 떄, 두 그래프 요소로 나뉠수 있는지는 루트와 단말 노드인지를 판단하면 된다.

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine()); // 정점의 개수
		List<Integer> adj[] = new List[n + 1];
		for (int i = 1; i <= n; i++) {
			adj[i] = new ArrayList<>();
		}

		// 간선의 정보 입력받기
		List<int[]> edges = new ArrayList<>();
		for (int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

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

		int q = Integer.parseInt(reader.readLine()); // 질의문의 개수
		StringBuilder answers = new StringBuilder();
		// t,k입력 t=: [1,2] - 1:단절점인지 , 2:단절선인지
		for (int i = 0; i < q; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int t = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			if (t == 1) {
				// 루트 또는 말단 노드일 때는 NO
				if (isRootOrTerminateNode(adj[k])) {
					answers.append("no");
				} else {
					answers.append("yes");
				}

			} else if (t == 2) {
				// 가선은 어디를 잘라도 무조건 두개의 그래프로 나뉨.:= 간선은 두 정점을 연결하는 요소의 성질이므로
				answers.append("yes");
			}

			answers.append("\\n");
		}
		System.out.println(answers);
	}

	/**
	 * 루트 또는 말단 노드는 인접리스트에 무조건 1개밖에 들어 있지 않는다.
	 * @param adj
	 * @return
	 */
	private static boolean isRootOrTerminateNode(List<Integer> adj) {
		int cnt = 0;

		for (Integer next : adj) {
			cnt++;
		}

		return cnt <= 1;
	}