(4803) 트리

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

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

---

문제 풀이

해당 문제는 트리 자료구조로 해결 할 수 있는 문제이다. 

 

트리 구조는 계층 구조로 그래프처럼 순환하는 그래프가 아니다. 그래서 해당 문제에서는 순환하는 그래프 인경우 트리의 수에서 제외 해야 하는 약간 까다로운 문제이다. 

 

이전에 방문 했던 노드를 다시 방문 하게 되었을 때를 순환한다는 조건으로 보고 조건식을 짜야한다. 

---

나의 답안

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int tc = 0;
        while (true) {
            int n = sc.nextInt();
            int e = sc.nextInt();
            if (n == 0 && e == 0) break;

            graph = new ArrayList[n + 1];
            visited = new boolean[n + 1];

            for (int i = 0; i < n + 1; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < e; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();

                graph[u].add(v);
                graph[v].add(u);
            }

            int cnt = 0;
            for (int i = 1; i < n + 1; i++) {
                if (!visited[i]) {
                    if (dfs(i, 0)) continue;
                    cnt++;
                }
            }

            tc++;
            if (cnt == 0) {
                sb.append("Case " + tc + ": No trees.\n");
            } else if (cnt == 1) {
                sb.append("Case " + tc + ": There is one tree.\n");
            } else {
                sb.append("Case " + tc + ": A forest of " + cnt + " trees.\n");
            }
        }
        System.out.print(sb.toString());

    }

    private static boolean dfs(int node, int parent) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (next == parent) continue;
            if (visited[next]) return true;
            if (dfs(next, node)) return true;
        }

        return false;
    }
}