www.youtube.com/playlist?list=PLDV1Zeh2NRsBI1C-mR6ZhHTyfoEJWlxvq Union Find [Disjoint Set] Playlist Playlist of videos explaining the union find (disjoint set) data structure. www.youtube.com
1. Adjacency Matrix 그래프의 각 노드(혹은 vertex)들을 x축, y축에 나열하고 x,y의 교점에 두 노드의 연결 여부를 표시한다. 0 1 2 3 4 0 0 1 0 0 1 1 1 0 1 1 1 2 0 1 0 1 0 3 0 1 1 0 1 4 1 1 0 1 0 장점 a, b의 연결 여부를 확인할 때 O(1) 밖에 걸리지 않는다. a, b의 연결 여부를 변경할 때 O(1) 밖에 걸리지 않는다. 단점 O(V^2)의 공간을 차지한다 (V = Vertex) 노드를 추가 혹은 제거할 때 O(V^2)만큼 소요된다. 2. Adjacency List 그래프의 각 노드별로 그 노드와 연결되어있는 다른 노드들의 정보가 담긴 리스트를 만들고, 이 리스트들을 하나로 모은다. *노드 목록 구현은 리스트/다이나믹 ..
