https://www.acmicpc.net/problem/1922
initial
A typical MST question. Review other mst blog posts that I wrote for this kruskal implementation (that is like dijkstra but with heap)
Just one precaution is that for the last code, we should be checking if next_b is not visited, not next_a cuz we already checked that in the above visited logic.
solution
from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = defaultdict(list)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append([c, a, b])
graph[b].append([c, b, a])
heap = graph[1]
heapq.heapify(heap)
ans = 0
visited = [False for _ in range(n + 1)]
visited[1] = True
while heap:
c, a, b = heapq.heappop(heap)
if not visited[b]:
visited[b] = True
ans += c
for hola in graph[b]:
next_c, next_a, next_b = hola
if not visited[next_b]:
heapq.heappush(heap, hola)
print(ans)complexity
v+e time and nope lol
To analyze the time and space complexity of your code:
Time Complexity:
- Building the graph: Constructing the graph takes O(m) time, where m is the number of edges in the graph.
- Heap Initialization: Initializing the heap with edges connected to node 1 takes O(deg(1)) time, where deg(1) is the degree of node 1.
- While Loop: The while loop runs until the heap is empty, and each iteration takes O(logm) time for popping from the heap and potentially O(deg(b)) time for iterating over neighbors of the current node, where deg(b) is the degree of the current node. Since each edge is processed at most twice (once for each of its incident nodes), the total time complexity for this loop is O(mlogm).
- Total time complexity: O(mlogm), dominated by the while loop.
Space Complexity:
- Graph Representation: The graph is represented using a dictionary, which requires O(m) space to store all edges.
- Heap Space: The heap requires O(deg(1)) space initially, but it can grow up to O(m) in the worst case if all edges are incident to node 1.
- Other variables: The space used by other variables like
ans,visited, and loop variables is O(n) since they have a size proportional to the number of nodes. - Total space complexity: O(m) for the graph + O(m) for the heap + O(n) for other variables = O(m + n).
Overall, the time complexity of your code is O(mlogm) and the space complexity is O(m + n).
