이번 문제는 BFS를 통해 해결하였다. 처음에는 유니온-파인드로 해결하려 하였지만, 사이클을 따로 확인해야 하는 불편함이 발생하였다. 그래서 BFS를 통해 접근하였다. 그래프를 인접 리스트로 저장하고, BFS를 통해 탐색하며 방문처리를 해준다. 만약 현재 노드가 이미 방문한 노드일 경우, flag를 False로 변환해준다. 중요한 포인트는 여기서 탐색을 종료하면 안된다. 왜냐하면 이 사이클과 연결된 모든 노드는 트리가 될 수 없기 때문이다. 연결된 모든 노드를 확인한 후에 flag를 반환해주어 해당 트리의 여부를 나타내주었다. 방문처리되지 않은 경우에만 탐색을 진행하였고, 반환된 결과가 True일 때에만 결과 변수를 1 증가시켰다.

Code

from collections import deque
def chk_tree(cur):
    q = deque()
    q.append(cur)
    flag = True
    while q:
        node = q.popleft()
        if visited[node]:
            flag = False
        visited[node] = True
        for nxt in graph[node]:
            if not visited[nxt]:
                q.append(nxt)
    return flag
num = 1
while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    visited = [False for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        if a == b:
            continue
    answer = 0
    for i in range(1, n+1):
        if not visited[i]:
            if chk_tree(i):
                answer += 1
    if answer > 1:
        print("Case "+str(num)+": A forest of "+str(answer)+" trees.")
    elif answer == 1:
        print("Case "+str(num)+": There is one tree.")
    else:
        print("Case "+str(num)+": No trees.")
    num += 1