π μλ‘μ μ§ν©(Disjoint Sets)
- μλ‘μ λΆλΆ μ§ν©λ€λ‘ λλμ΄μ§ μμλ€μ λ°μ΄ν°λ₯Ό μ²λ¦¬νκΈ° μν μλ£κ΅¬μ‘°
- μλ‘μ μ§ν© μ 보(ν©μ§ν© μΈμ°)κ° μ£Όμ΄μ‘μ λ νΈλ¦¬ μλ£ κ΅¬μ‘°λ₯Ό μ΄μ©ν΄ μ§ν©μ ννν¨
- union(ν©μ§ν©) : μ°μ°μ νμΈνλ©°, μλ‘ μ°κ²°λ λ λ
Έλ νμΈ
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent, parent[x])
return x
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
v, e = map(int, input().split())
parent = [i for i in range(v+1)]
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
print("κ° μμκ° μν μ§ν© : ", end="")
for i in range(1, v+1):
print(find_parent(parent, i), end=" ")
print()
print("λΆλͺ¨ ν
μ΄λΈ : ", end="")
for i in range(1, v+1):
print(parent[i], end=' ')
π κ²½λ‘ ν¨μΆμ μ¬μ©ν μλ‘μ μ§ν© μκ³ λ¦¬μ¦
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
v, e = map(int, input().split())
parent = [i for i in range(v+1)]
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
print("κ° μμκ° μν μ§ν© : ", end="")
for i in range(1, v+1):
print(find_parent(parent, i), end=" ")
print()
print("λΆλͺ¨ ν
μ΄λΈ : ", end="")
for i in range(1, v+1):
print(parent[i], end=' ')
πμ¬μ΄ν΄ νλ³ μκ³ λ¦¬μ¦
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent, parent[x])
else:
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
cycle = False
for i in range(e):
a, b = map(int, input().split())
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union_parent(parent, a, b)
if cycle:
print("μ¬μ΄ν΄ λ°μ")
else:
print("μ¬μ΄ν΄ λ
Έλ°μ")
π μ μ₯ νΈλ¦¬
- νλμ κ·Έλνκ° μμ λ λͺ¨λ λ
Έλλ₯Ό ν¬ν¨νλ©΄μ μ¬μ΄ν΄μ΄ μ‘΄μ¬νμ§ μλ λΆλΆ κ·Έλν
π ν¬λ£¨μ€μΉΌ μκ³ λ¦¬μ¦
- μ΅μ μ μ₯νΈλ¦¬ μκ³ λ¦¬μ¦μΌλ‘ κ°μ₯ μ μ λΉμ©μΌλ‘ λͺ¨λ λ
Έλλ₯Ό μ°κ²°νλ κ·Έλν μκ³ λ¦¬μ¦μΌλ‘ λΆλ₯λλ€.
- ꡬ체μ μΈ μκ³ λ¦¬μ¦μ μλμ κ°λ€.
- κ°μ λ°μ΄ν
λ₯Ό λΉμ©μ λ°λΌ μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλ€.
- κ°μ μ νλμ© νμΈνμ¬ νμ¬μ κ°μ μ΄ μ¬μ΄ν΄μ λ°μμν€λμ§ νμΈνλ€.
- λ§μ½ μ¬μ΄ν΄μ΄ λ°μνλ κ²½μ° μ΅μ μ μ₯ νΈλ¦¬μ ν¬ν¨μν¨λ€.
- μ¬μ΄ν΄μ΄ λ°μνμ§ μλ κ²½μ° μ΅μ μ μ₯ νΈλ¦¬μ ν¬ν¨μν€μ§ μλλ€.
- λͺ¨λ κ°μ μ λν΄ μμ κ³Όμ μ λ°λ³΅νλ€.
- ν¬λ£¨μ€μΉΌ μκ³ λ¦¬μ¦ μκ° λ³΅μ‘λ :
O(ElogE)
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent, parent[x])
else:
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a<b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0]*(v+1)
edges = []
result = 0
for i in range(1, v+1):
parent[i] = i
for i in range(e):
a, b, cost = map(int, input().split())
edges.append((cost,a,b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
π μμ μ λ ¬
- λ°©ν₯ κ·Έλνμ λͺ¨λ λ
Έλλ₯Ό βλ°©ν₯μ±μ κ±°μ€λ₯΄μ§ μλλ‘ μμλλ‘ λμ΄νλ κ²
- μμκ° μ ν΄μ Έ μλ μΌλ ¨μ μμ
μ μ°¨λ‘λ‘ μνν΄μΌ ν λ μ¬μ©νλ€.
- μ§μ
μ°¨μ : νΉμ ν λ
Έλλ‘ λ€μ΄μ€λ κ°μ μ κ°μ
- μμ μ λ ¬ μκ³ λ¦¬μ¦
- μ§μ
μ°¨μκ° 0μΈ λ
Έλλ₯Ό νμ λ£λλ€.
- νμμ μμλ₯Ό κΊΌλ΄ ν΄λΉ λ
Έλμμ μΆμνλ κ°μ μ κ·Έλνμμ μ κ±°νλ€.
- μλ‘κ² μ§μ
μ°¨μκ° 0μ΄ λ λ
Έλλ₯Ό νμ λ£λλ€
- νκ° λΉλκΉμ§ λ°λ³΅νλ€.
- μμμ λ ¬ μκ°λ³΅μ‘λ :
O(ElogE)
from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v+1)
graph =[[] for i in range(v+1)]
for i in range(e):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
def topology_sort():
result = []
q = deque()
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()