728x90
반응형
문제 바로가기
문제:
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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 heapq, sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
def find(node):
if node != parent[node]:
parent[node] = find(parent[node])
return parent[node]
def union(x, y):
nx = find(x)
ny = find(y)
if nx < ny:
parent[ny] = nx
else:
parent[nx] = ny
case = 0
while True:
case += 1
n, m = map(int, sys.stdin.readline().split(" "))
if n == 0 and m == 0:
break
graph = [[] for _ in range(n + 1)]
parent = [i for i in range(n + 1)]
# union-find 함수
cycle = set()
for _ in range(m):
a, b = map(int, sys.stdin.readline().rstrip().split(" "))
# find (cycle)
if find(a) == find(b):
cycle.add(parent[a])
cycle.add(parent[b])
# 둘 중 하나라도 사이클에 들어있으면 어차피 사이클임
if parent[a] in cycle or parent[b] in cycle:
cycle.add(parent[a])
cycle.add(parent[b])
# union
union(a, b)
# 경로 압축
for i in range(n+1):
find(i)
parent = set(parent)
res = len(parent - cycle) - 1
if res == 0:
print('Case %d: No trees.' % case)
elif res == 1:
print('Case %d: There is one tree.' % case)
else:
print('Case %d: A forest of %d trees.' % (case, res))
이 문제는 부모 노드가 다른 것의 개수를 구하는 문제같다.
유니온 파인드를 사용하여 두 노드의 부모가 같다면 싸이클에 포함된다는 뜻이다.
또 두 노드 중에 하나라도 싸이클에 들어있으면 결국 싸이클에 포함되므로 싸이클 set에 넣어준다.
반응형
댓글