문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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. |
풀이
사이클을 제외한 그래프, 즉 트리의 개수를 세는 문제이다.
따라서 방문 정점을 활용한 그래프 탐색 혹은 유니온 파인드 두 가지 방법으로 풀이가 가능한 문제이다.
필자는 유니온 파인드로 풀이했으므로 해당 방법에 대해서 글을 작성한다.
각 간선을 입력받을 때마다 유니온 파인드를 통해 사이클을 판별한다.
사이클이 맞다면 두 정점을 사이클 리스트에 따로 저장해둔다.
간선 입력이 끝나면 find 함수를 통해 지금까지 바뀐 부모 노드들을 한 번 정리해 준다.
이후, parents 노드들을 순회하며 사이클에 포함되지 않은 그래프만 세준 뒤 출력한다.
import sys
input = sys.stdin.readline
def union(x,y):
x = find(x)
y = find(y)
if x < y:
parents[y] = x
else:
parents[x] = y
def find(x):
if x != parents[x]:
parents[x] = find(parents[x])
return parents[x]
idx = 0
while True:
idx += 1
n,m = map(int,input().split())
if n==0 and m==0:
break
parents = [i for i in range(n+1)]
cycle = set()
for _ in range(m):
a,b = map(int,input().split())
if find(a) == find(b):
cycle.add(parents[a])
cycle.add(parents[b])
# 두 정점 중 하나가 사이클에 포함되는 정점이라면 나머지 정점도 사이클로 포함한다.
if parents[a] in cycle or parents[b] in cycle:
cycle.add(parents[a])
cycle.add(parents[b])
union(a,b)
# find 함수를 쭉 돌려서 각 정점의 parents를 갱신한다.
for i in range(n+1):
find(i)
parents = set(parents)
ans = sum([1 if i not in cycle else 0 for i in parents])-1
if ans == 0:
print('Case %d: No trees.' %idx)
elif ans == 1:
print('Case %d: There is one tree.' %idx)
else:
print('Case %d: A forest of %d trees.' %(idx,ans))
'알고리즘 연습 > 트리' 카테고리의 다른 글
[🥇2 / 백준 2263 / 파이썬] 트리의 순회 (0) | 2022.04.10 |
---|---|
[🥇5 / 백준 1068 / 파이썬] 트리 (0) | 2022.01.30 |
[🥈1 / 백준 1991 / 파이썬] 트리 순회 (0) | 2021.12.04 |
[🥇3 / 백준 1167 / 파이썬] 트리의 지름 (2) | 2021.10.05 |
[🥇4 / 백준 1967 / 파이썬] 트리의 지름 (0) | 2021.10.05 |