문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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."를 테스트 케이스 번호와 함께 출력한다.
예제
입력
6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0
출력
Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.
풀이
from collections import deque
def check(num): # num으로 받은 노드가 트리인지 확인하는 함수
visited[num] = True # 이제 방문함.
queue = deque([num]) # BFS를 위한 queue
while queue:
node = queue.popleft() # 노드 가져옴
for n_node in trees[node]: # bfs. 해당 노드에 연결된 노드들 차례로 가져옴.
if trees[node][n_node] == 0: # 엣지 체크 (0: 체크 안함, 1: 체크함)
if not visited[n_node]: # 해당 노드에 처음 방문
visited[n_node] = True
queue.append(n_node) # 대기열에 다음 노드 추가
trees[node][n_node] = 1 # 엣지 체크
trees[n_node][node] = 1 # 엣지 체크
else:
return False # 헤당 노드에 방문한 적이 있으므로 이는 트리가 아닌 그래프
return True
test = 0
while True:
test += 1
N, M = map(int, input().split())
if N == 0 and M == 0: # 0 0 입력시 종료
break
edges = [list(map(int, input().split())) for _ in range(M)]
visited = [False] * (N + 1) # 방문여부 확인용
trees = [{} for _ in range(N+1)] # 노드 별 연결된 엣지 모음
for e in edges:
trees[e[0]][e[1]] = 0 # 엣지 체크. 0: 체크X / 1: 체크 O
trees[e[1]][e[0]] = 0
cnt = 0 # 트리 갯수
for num in range(1, N + 1): # 모든 노드 확인
if not visited[num]: # 해당 노드 방문 안한 경우
if check(num): # 트리인지 체크함
cnt += 1
# 출력
print("Case {}: ".format(test), end="")
if cnt == 0:
print("No trees.")
elif cnt == 1:
print("There is one tree.")
else:
print("A forest of {} trees.".format(cnt))
python3로 제출하면 시간 초과가 나오고 pypy3로 제출하면 잘 된다. python3로 하는 방법이 있을지 공부해봐야 함.