* 개선된 서로소 집합 알고리즘 소스 코드*
import sys
input=sys.stdin.readline
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
if parent[x]!=x:
parent[x] = find_parent(parent,parent[x])
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=[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=' ')
* 서로소 집합을 활용한 사이클 판별 소스 코드 *
import sys
input=sys.stdin.readline
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
if parent[x]!=x:
parent[x] = find_parent(parent,parent[x])
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=[i for i in range(v+1)]
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("사이클이 발생하지 않았습니다.")
* 최소 신장 트리 : 크루스칼 알고리즘 소스 코드*
- 양방향 이동에만 사용 가능하다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.
import sys
input=sys.stdin.readline
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
if parent[x]!=x:
parent[x] = find_parent(parent,parent[x])
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=[i for i in range(v+1)]
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges=[]
result=0
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이 된 노드를 큐에 넣는다.
import sys
input=sys.stdin.readline
from collections import deque
# 노드의 개수와 간선의 개수를 입력받기
v,e=map(int,input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree=[0]*(v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph=[[] for i in range(v+1)]
# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a,b=map(int,input().split())
graph[a].append(b)
indegree[b]+=1
# 위상 정렬 함수
def topology_sort():
result=[] # 알고리즘 수행 결과를 담을 리스트
q=deque()
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1,v+1):
if indegree[i]==0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
now=q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 뺴기
for i in graph[now]:
indegree[i]-=1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i]==0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in result:
print(i,end=" ")
topology_sort()
01. 팀 결성(서로소 집합)
import sys
input=sys.stdin.readline
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
if parent[x]!=x:
parent[x] = find_parent(parent,parent[x])
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=[i for i in range(v+1)]
for i in range(e):
distinct,a,b=map(int,input().split())
if distinct==0:
union_parent(parent,a,b)
else:
if find_parent(parent,a)!=find_parent(parent,b):
print('NO')
else:
print('YES')
02. 도시 분할 계획
import sys
input=sys.stdin.readline
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
if parent[x]!=x:
parent[x] = find_parent(parent,parent[x])
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=[i for i in range(v+1)]
edges=[]
total=0
last=0 # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
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)
total+=cost
last=cost
print(total-last)
03. 커리큘럼
import sys
input=sys.stdin.readline
from collections import deque
import copy
# 노드의 개수 입력받기
v=int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree=[0]*(v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph=[[] for i in range(v+1)]
time=[0]*(v+1)
# 모든 정보를 입력받기
for i in range(1,v+1):
tmp=list(map(int,input().split()))
time[i]=tmp[0]
for x in tmp[1:-1]:
indegree[i]+=1
graph[i].append(x)
# 위상 정렬 함수
def topology_sort():
result=copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
q=deque()
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1,v+1):
if indegree[i]==0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
now=q.popleft()
# 해당 원소와 연결된 노드들의 진입차수에서 1 뺴기
for i in graph[now]:
result[i]=max(result[i],result[now]+time[i])
indegree[i]-=1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i]==0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in range(1,v+1):
print(result[i])
topology_sort()