[4803] 트리

🔗 문제 링크

https://www.acmicpc.net/problem/4803

🔍 문제 설명

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

⚠️ 제한사항

• n ≤ 500

• m ≤ n(n-1)/2

• 1 ≤ K ≤ 300,000

• 1 ≤ X ≤ N

• 1 ≤ A, B ≤ N

---

🗝 풀이 (언어 : Java)

노드를 N, 간선을 E라고 하면 N = E+1의 공식이 발생하는데, 이 성질을 이용해 방문하지 않은 노드를 확인하면서 트리의 개수를 카운트한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static final String PRINT_FORMAT = "Case %d: %s";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int order = 1;
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int circle = Integer.parseInt(st.nextToken());
            int line = Integer.parseInt(st.nextToken());
            List<Integer>[] edges = new ArrayList[circle + 1];
            for (int i = 0; i < edges.length; i++) {
                edges[i] = new ArrayList<>();
            }
            for (int i = 0; i < line; i++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
                int start = Integer.parseInt(st2.nextToken());
                int end = Integer.parseInt(st2.nextToken());
                edges[start].add(end);
                edges[end].add(start);
            }
            if (circle == 0 && line == 0) {
                br.close();
                break;
            }
            solution(circle, edges, order++);
        }
    }

    private static void solution(int circle, List<Integer>[] edges, int order) {
        boolean[] visited = new boolean[circle + 1];
        int count = 0;
        for (int start = 1; start <= circle; start++) {
            if (visited[start]) {
                continue;
            }
            int node = 0;
            int edge = 0;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int current = queue.poll();
                if (visited[current]) {
                    continue;
                }
                visited[current] = true;
                node++;
                for (int next : edges[current]) {
                    edge++;
                    if (!visited[next]) {
                        queue.add(next);
                    }
                }
            }
            count += (edge / 2) + 1 == node ? 1 : 0;
        }
        System.out.println(String.format(PRINT_FORMAT, order, printAnswer(count)));
    }

    private static String printAnswer(int count) {
        if (count == 0) {
            return "No trees.";
        }
        if (count == 1) {
            return "There is one tree.";
        }
        return String.format("A forest of %d trees.", count);
    }

}