Scribbling

1. 무향 그래프 내 Cycle 판별 - 서로소 집합 알고리즘을 사용한다. - 모든 edge에 대해 두 node의 부모가 같다면, cycle이 존재. 두 node의 부모가 다르다면, union 진행. v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a]..

v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: pa..

Set 자료형: 중복을 제거해준다. mySet = set([1, 2, 3]) 1) 데이터 추가 mySet.add(3) mySet.update([4, 5, 6]) 2) 데이터 삭제 mySet.remove(3): set에 3이 없으면 error mySet.discard(3): set에 3이 없어도 no error 3) Set에 데이터 추가/삭제는 O(1)

최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq = [] heapq.heappush(pq, (0, start)) distance[start] = 0 while pq: dist_u, u = heapq.heappop(pq) # node u가 이미 처리된 경우 if distance[u] dist_uv + dist_u: distance[v] = dist_uv + dist_u heapq.heappush(pq, (..