백준 6416 - 트리인가?

문제

문제 링크

풀이

트리인지 확인하기 위해서 다음 2가지를 검사한다.

1. Root가 1개인지 검사한다.
2. V로 들어오는 간선이 2개 이상인지 확인한다.

트리는 Root가 1개이어야한다.
또한 V로 들어오는 간선도 1개이어야 한다.
2개 이상이면 사이클이 발생할 수도 있다.

문제에서는 트리의 노드 번호를 특정할 수 없으므로 배열을 사용할 수 없다.
그래서 Set을 이용해 문제를 해결했다.

코드

java

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        Set<Integer> destinations = new HashSet<>();
        Set<Integer> departures = new HashSet<>();
        boolean isTree = true;
        int k = 1;

        while (true) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            if (u < 0 && v < 0) {
                break;
            }

            if (u == 0 && v == 0) {
                if (departures.isEmpty()) {
                    sb.append("Case ").append(k++).append(" is a tree.\n");
                    continue;
                }

                int rootCnt = 0;
                for (int vertex : departures) {
                    if (!destinations.contains(vertex)) {
                        rootCnt++;
                    }
                }

                if (rootCnt != 1) {
                    isTree = false;
                }

                sb.append("Case ").append(k++);
                if (isTree) {
                    sb.append(" is a tree.\n");
                } else {
                    sb.append(" is not a tree.\n");
                }
                destinations.clear();
                departures.clear();
                isTree = true;
                continue;
            }

            if (!destinations.add(v)) {
                isTree = false;
            }
            departures.add(u);
        }

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

}