동블

그래프 뷰

08. 그래프-MST-UnionFind

4 min read

그래프 - MST / Union-Find

Summary

같은 그룹인지 확인, 그룹 합치기, 무방향 사이클 판별은 Union-Find다.
모든 정점을 최소 비용으로 연결은 MST이고, 보통 Kruskal을 먼저 쓴다.

Union-Find 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] parent;
    static int[] rank;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        makeSet(n);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            if (op == 0) {
                union(a, b);
            } else {
                sb.append(find(a) == find(b) ? "YES" : "NO").append('\n');
            }
        }
 
        System.out.print(sb);
    }
 
    static void makeSet(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
 
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
 
    static boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
 
        if (rootA == rootB) return false;
 
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
 
        return true;
    }
}

Kruskal MST 검증 템플릿

Warning

MST는 간선을 V - 1개 선택해야 한다.
끝까지 선택하지 못하면 모든 정점을 연결할 수 없는 그래프다.

import java.io.*;
import java.util.*;
 
public class Main {
    static class Edge {
        int a, b;
        long cost;
 
        Edge(int a, int b, long cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }
 
    static int[] parent;
    static int[] rank;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
 
        Edge[] edges = new Edge[e];
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long cost = Long.parseLong(st.nextToken());
            edges[i] = new Edge(a, b, cost);
        }
 
        Arrays.sort(edges, (x, y) -> Long.compare(x.cost, y.cost));
        makeSet(v);
 
        long answer = 0;
        int count = 0;
 
        for (Edge edge : edges) {
            if (union(edge.a, edge.b)) {
                answer += edge.cost;
                count++;
                if (count == v - 1) break;
            }
        }
 
        System.out.println(count == v - 1 ? answer : "DISCONNECTED");
    }
 
    static void makeSet(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
 
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
 
    static boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
 
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }
}

문제 신호

표현의심
같은 집합인지 확인Union-Find
두 집합 합치기Union-Find
무방향 그래프 사이클Union-Find
모든 도시를 최소 비용으로 연결MST
네트워크 구성 비용 최소Kruskal / Prim

주의점

실수주의
find 없이 parent 변경반드시 대표자끼리 합치기
경로 압축 없음시간초과 위험
방향 그래프 사이클에 사용위상정렬을 먼저 의심
MST 연결 불가 미체크count == V - 1 확인
비용 합 intlong answer 사용

백지 복원

1. union 전에 find를 해야 하는 이유는?
2. Kruskal에서 간선을 어떤 순서로 보는가?
3. MST에서 선택되는 간선 수는?
4. union이 false이면 어떤 의미인가?

관련 문서