문제
https://www.acmicpc.net/problem/4803
접근
- 주어진 연결정보에 따라 노드를 분리하고 각 노드 집합에 대해 사이클이 발생하는지 확인하면 트리인지 아닌지 판별할 수 있으므로 유니온 파인드를 이용했다.
- 만약 사이클이 생긴다면 한 노드에서 다른 노드로 갈 수 있는 경로가 2개 이상이 되므로, 노드 집합의 원소의 개수가 k라고 한다면 노드 집합의 간선의 개수가 k-1보다 크다는 뜻
- 또한 노드를 연결정보에 따라 분리했으므로 사이클 조건만 만족한다면 루트 노드는 노드 안에서 항상 한개 이므로 따로 확인하지 않았다.
풀이
- 간선 정보를 입력받고 만약 사이클이 발생한다면 사이클이 발생한 노드의 부모 노드 정보를 저장한다.
- 이후 모든 노드들에 대해 부모 노드가 사이클이 발생한 노드가 아니라면 tree이므로 tree 집합에 저장한다.
- 고려할 반례는 이미 사이클이 존재하는 그래프에 새로운 노드를 연결할 경우, 해당 노드의 부모 노드 또한 사이클 집합에 추가해야 한다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
parent[b] = a
else:
parent[a] = b
t = 1
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
parent = [i for i in range(n + 1)]
cycle = set()
for _ in range(m):
a, b = map(int, input().split())
x, y = find(a), find(b)
if x == y:
cycle.add(x)
elif x in cycle or y in cycle:
cycle.add(x)
cycle.add(y)
union(a, b)
tree = set()
for i in range(1, n + 1):
x = find(i)
if x not in cycle:
tree.add(x)
ans = len(tree)
if ans == 0:
print("Case {}: No trees.".format(t))
elif ans == 1:
print("Case {}: There is one tree.".format(t))
else:
print("Case {}: A forest of {} trees.".format(t, ans))
t += 1
'Python > Coding Test' 카테고리의 다른 글
19844 단어 개수 세기 (0) | 2022.03.07 |
---|---|
22943 수 (0) | 2022.03.01 |
19641 중첩 집합 모델 (0) | 2022.02.28 |
22871 징검다리 건너기 (large) (0) | 2022.02.27 |
22869 징검다리 건너기 (small) (0) | 2022.02.27 |