(전공복습) 데이터과학 4. 시각화
차례
기초적인 유니온-파인드(Union-Find, Disjoint Set) 문제.
주어진 연산이 0
이면 유니온, 1
이면 파인드를 하면 되는 기초적인 문제이다.
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)
n, m = map(int, input().split())
# 파인드
def root(node):
if parent[node] != node:
parent[node] = root(parent[node])
return parent[node]
# 유니온
def union(a, b):
ra, rb = root(a), root(b)
parent[ra] = parent[rb] = min(ra, rb)
parent = [i for i in range(n+1)]
for _ in range(m):
op, a, b = map(int, input().split())
if op == 0:
union(a, b)
else:
print('YES' if root(a) == root(b) else 'NO')
문제 링크 문제 링크
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...