최소신장tree

64번

65번

66번 불우이웃돕기

** 최소신장트리 MST는 두가지 알고리즘으로 풀이가 가능하다

우선순위큐 동작방법(이 형태에서 항상 변형)

PriorityQueue<Edge> pq = new PriorityQueue<>();
boolean[] visited = new boolean[N];
int mst = 0;
int connected = 0;

// 0번 정점부터 시작
visited[0] = true;
for (Edge e : graph[0]) {
    pq.add(e);
}

while (!pq.isEmpty() && connected < N - 1) {
    Edge cur = pq.poll();
    if (visited[cur.to]) continue;

    visited[cur.to] = true;
    mst += cur.weight;
    connected++;

    for (Edge next : graph[cur.to]) {
        if (!visited[next.to]) {
            pq.add(next);
        }
    }
}