이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 94 번째 글 입니다.
목차
골드2 : union find 문제이다.
풀이
으으 너무 아쉽다. 잘해놓고 같은 친구가 들어올 경우에 계산이 중복된다는 것을 체크하지 못했다.
그리고 지나고 보니 코드가 더러워서 다시짰다.
Code
import sys
input = sys.stdin.readline
parent = []
def find(x):
if parent[x][0] == x:
return x
else:
parent[x][0] = find(parent[x][0])
return parent[x][0]
def union(x, y):
px, py = find(x), find(y)
if px < py:
parent[py][0] = px
parent[px][1] += parent[py][1]
else:
parent[px][0] = py
parent[py][1] += parent[px][1]
T = int(input())
for _ in range(T):
f = int(input())
name_dict = dict()
num = 0
parent = []
for _ in range(f):
a, b = input().split()
if a not in name_dict:
name_dict[a] = num
parent.append([num, 1])
num += 1
if b not in name_dict:
name_dict[b] = num
parent.append([num, 1])
num += 1
if find(name_dict[a]) != find(name_dict[b]):
union(name_dict[a], name_dict[b])
print(parent[find(name_dict[a])][1])
import sys
input = sys.stdin.readline
parent = dict()
network = dict()
def find(x):
if parent[x] == x:
return x
else:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
# parent[py] = px
# network[px] += network[py]
npx, npy = network[px], network[py]
if npx >= npy:
parent[py] = px
network[px] += network[py]
else:
parent[px] = py
network[py] += network[px]
t = int(input())
for _ in range(t):
f = int(input())
parent.clear()
network.clear()
for _ in range(f):
a, b = input().split()
if a not in parent:
parent[a] = a
network[a] = 1
if b not in parent:
parent[b] = b
network[b] = 1
union(a, b)
print(network[find(parent[a])])
마지막에 find(parent[a])로 검색해야 한다. union find 알고리즘을 보다보면, 한번에 계속해서 정확하게 부모 집합을 가리키기 못하기 때문이다.