4803. 트리 (Python)

4803번: 트리

 

풀이

 dfs를 통해서 연결된 그래프에 사이클이 있는지를 판단한다. 현재 정점과 연결되어 있는 정점 중 이미 방문한 정점이 있다면 이는 사이클이 존재하는 그래프임을 의미하므로 트리가 될 수 없다. 한 가지 주의할 건 dfs 함수를 호출할 때 현재 정점으로 오기 전에 있었던 정점의 정보를 같이 전달해서 사이클 유무를 판단할 때 해당 정점을 제외하고 판별할 수 있게 해야 한다.

 

코드

import sys
input = sys.stdin.readline


# 사이클을 판단하기 위한 함수
# now: 현재 정점, prev: 현재 정점으로 오기 전에 방문했던 정점
def dfs(now, prev):
    visited[now] = True  # 현재 정점 방문 체크

    for i in graph[now]:  # now 정점과 연결되어 있는 정점들에 대해서
        if i == prev:  # 이전 정점인 경우는 방문 체크에서 제외
            continue

        if visited[i]:  # 이미 방문한 정점이 있다면 사이클이 존재함을 의미
            global isTree
            isTree = False  # 사이클이 존재하므로 트리가 될 수 없다.
            return

        dfs(i, now)


if __name__ == '__main__':
    testCase = 1
    while True:
        N, M = map(int, input().split())

        if N == 0 and M == 0:
            break

        graph = [[] for _ in range(N + 1)]
        visited = [False for _ in range(N + 1)]

        for _ in range(M):
            a, b = map(int, input().split())
            graph[a].append(b)
            graph[b].append(a)

        treeCnt = 0
        for i in range(1, N+1):
            if visited[i]:
                continue

            isTree = True
            dfs(i, 0)

            if isTree:
                treeCnt += 1

        print('Case %d:' % testCase, end=' ')
        if treeCnt == 0:
            print('No trees.')
        elif treeCnt == 1:
            print('There is one tree.')
        else:
            print('A forest of %d trees.' % treeCnt)

        testCase += 1