[백준] 4803 트리 (파이썬 python)

 

 

문제 링크

 

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

4803번: 트리

 

 

문제 풀이

 

트리는 사이클이 없는 연결 요소입니다.

결국 반대로 사이클을 판별하여 트리가 아닌 것들을 찾아내면 문제를 해결할 수 있습니다.

한 노드씩 순차적으로 확인하되 이전에 방문하지 않은 노드들을 확인합니다.

find_cycle(start) 함수는 사이클이 존재할 경우 flag에 True를 담아 반환하고

해당 사이클에 존재하는 모든 노드의 방문 처리 배열 값을 1로 변환합니다.

사이클에 존재하는 노드들을 한번에 방문처리함으로써 탐색 횟수를 줄일 수 있습니다.

문제에서 발생할 수 있는 예외로,

간선의 정보를 입력할 때 입력되는 두 노드가 다른 노드라는 조건이 없으므로

같은 노드 두개가 입력될 수 있습니다.

이 경우 한 노드 내에서 사이클이 발생하므로 트리가 될 수 없고,

그 노드와 연결된 모든 노드들 역시 사이클이 존재하는 연결에 포함되어 트리가 될 수 없습니다.

 

 

전체 코드

from collections import deque

def find_cycle(start):
    flag = False
    q = deque()
    q.append(start)
    while q:
        now = q.popleft()
        if visited[now]:
            flag = True
        visited[now] = 1
        for node in graph[now]:
            if node == now:
                flag = True
            if not visited[node]:
                q.append(node)
    return flag

case = 1
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = [[] for _ in range(n + 1)]
    visited = [0] * (n + 1)
    result = 0
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1, n + 1):
        if not visited[i]:
            if not find_cycle(i):
                result += 1
    if result == 0:
        print("Case {}: No trees.".format(case))
    elif result == 1:
        print("Case {}: There is one tree.".format(case))
    else:
        print("Case {}: A forest of {} trees.".format(case, result))
    case += 1