최소 신장 트리

/* ── 가중치 오름차순 정렬 후, 사이클을 안 만들면 추가 ──────── */
public int kruskal(int n, int[][] edges) {  // edges[i] = {u, v, weight}
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);   // 가중치 기준 정렬
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    int totalWeight = 0, edgeCount = 0;
    for (int[] e : edges) {
        int ru = find(parent, e[0]), rv = find(parent, e[1]);
        if (ru != rv) {                     // 서로 다른 그룹 → 연결해도 사이클 없음
            parent[ru] = rv;
            totalWeight += e[2];
            edgeCount++;
            if (edgeCount == n - 1) break;  // 간선을 n-1개 모으면 완성
        }
    }
    return totalWeight;
}

private int find(int[] parent, int x) {
    while (parent[x] != x) x = parent[x];   // x가 속한 그룹의 대표 노드 찾기
    return x;
}

/* ── "누적 거리" 대신 "트리에 연결하는 간선 하나의 가중치"만 비교 ── */
public int prim(int n, List<List<int[]>> adj, int start) {
    boolean[] inTree = new boolean[n];
    int[] minEdge = new int[n];
    Arrays.fill(minEdge, Integer.MAX_VALUE);
    minEdge[start] = 0;

    int totalWeight = 0;
    for (int count = 0; count < n; count++) {
        int u = -1;
        for (int i = 0; i < n; i++) {          // 트리 밖에서 연결 비용이 가장 싼 노드 탐색
            if (!inTree[i] && (u == -1 || minEdge[i] < minEdge[u])) u = i;
        }
        inTree[u] = true;
        totalWeight += minEdge[u];

        for (int[] edge : adj.get(u)) {          // u의 인접 간선으로 연결 비용 갱신
            int v = edge[0], w = edge[1];
            if (!inTree[v] && w < minEdge[v]) minEdge[v] = w;
        }
    }
    return totalWeight;
}

/* ── find할 때마다 트리를 납작하게 눌러 다음 find를 더 빠르게 ── */
private int findCompressed(int[] parent, int x) {
    if (parent[x] != x) {
        parent[x] = findCompressed(parent, parent[x]);  // 재귀로 대표 노드를 찾은 뒤
    }
    return parent[x];                    // x를 대표 노드에 직접 연결(경로 압축)
}