트리
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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."를 테스트 케이스 번호와 함께 출력한다.
import sys
sys.stdin = open("input.text", "rt")
def find_parent(x): #x노드의 부모(속하는 집합) 찾기
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
def union_parent(a,b): #a,b 노드를 합치기
a = find_parent(a)
b = find_parent(b)
if a < b: #b가 더 크면 b의 부모를 a로
parent[b] = a
else:
parent[a] = b
r = 1
while True:
n,m = map(int, input().split())
if n == 0 and m == 0:
break
parent = [0] * (n+1)
for i in range(1,n+1):
parent[i] = i
temp = []
cycle = False #사이클 판별을 위해
for _ in range(m):
a,b = map(int, input().split()) #a,b노드는 연결
a = find_parent(a)
b = find_parent(b)
if a == b:
cycle = True
temp.append(a)
else:
union_parent(a,b)
if a in temp or b in temp: #해당 집합이 사이클 집합에 포함되면 트리처리가 아니라 사이클 처리로 트리 개수에서 제외해야함.
temp.append(a)
temp.append(b) #두 정점 중 하나가 사이클에 포함되는 정점이라면 나저미 정점도 사이클로 포함.
# if find_parent(a) == find_parent(b): #중복 없이 처음으로 등장하는데
# #부모가 같다면. 사이클 발생.
# cycle = True
# a = find_parent(a) #a,b중 아무거나 부모 인덱스 받아와서 저장.
# temp.append(a) #사이클이 발생한 인덱스(집합) 따로 저장. 즉 해당 집합을 따로 저장.
# else:
# union_parent(a,b)
check = set(temp) #만약 사이클이 있다면 추가해야지.
for i in range(1,n+1):
find_parent(i) #부모 갱신 해줘야한다 ?
cnt = 0
for i in range(1,n+1):
if parent[i] in check: #사이클이 있는 집합은 check에 추가해놓고 나중에 방문 안해야함.
continue
cnt += 1 #해당 집합(트리) 개수 추가
check.add(parent[i]) #이제 해당 집합 포함시켰으니 다른 트리 찾아야지
#check에 추가시켜서 다음에 방문 또 안하도록.
if cnt == 0:
print(f"Case {r}: No trees.")
elif cnt == 1:
print(f"Case {r}: There is one tree.")
else:
print(f"Case {r}: A forest of {cnt} trees.")
r += 1
코멘트
핵심은 사이클을 형성한 노드의 번호를 따로 저장하고, 계속 a,b의 노드를 입력 받을 때 사이클 형성한 노드 리스트 안에 포함된다면 그 두 노드 모두 트리가 아닌 사이클 형성한 리스트 안에 추가해줬어야 했다. 이것 때문에 굉장히 많이 시간을 쏟았따....
그리고 모든 노드 집합 연결한 이후에 한번 더 부모 집합 확인했어야만 했다 !!!
for i in range(1,n+1):
find_parent(i) #부모 갱신 해줘야한다 ?find 함수 쭉 돌려서 각 정점의 parent 갱신.
유니온 파인드 문제로써 다시 풀어볼 문제이다.
