Union-Find (유니온 파인드)

이어지는 간선들을 하나의 집합으로 분류하고 서로소 집합들을 만드는 알고리즘이다. 

Disjoint Set이라고도 부른다.

 

핵심 함수

• find 함수 : 노드들의 부모를 찾는 과정, 어떤 집합에 포함되있는지 찾는다.
• union 함수 : 두 노드를 하나의 집합으로 묶는다.

---

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

public class Main {
    static int n, m, parent[];
 
    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
 
    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        parent[y] = x;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        parent = new int[n + 1];
 
        for (int i = 0; i <= n; i++)
            parent[i] = i;
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0, t, x, y; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            if (t == 0) {
                union(x, y);
            } else {
                sb.append(find(x) == find(y) ? "YES" : "NO").append("\n");
            }
        }
 
        System.out.println(sb);
 
        br.close();
    }
}

 

간과했던 부분 ( line : 38 )

두 노드가 같은 집합인지 확인할 때, find 함수를 통해 찾는다면 재귀를 다시 사용해야 했기 떄문에 불필요하다고 생각했고, parent 배열을 확인하여 O(1) 만에 같은 집합인지 알 수 있을 것이라고 생각했다. 

3 3
0 2 3
0 1 2
1 1 3

하지만 이러한 반례의 경우, 3의 부모는 2가 될 것이고, 2의 부모는 1이 될 것이다. 노드 1, 2, 3은 같은 집합이지만 1과 3노드가 같은 집합인지 확인할 경우 parent 배열에 다른 값이 들어 가있는 상태이고, 같은 집합임에 불구하고 NO를 출력했던 것이다. 따라서 같은 집합인지 확인하기 전 find를 호출하여 다시 루트노드까지 가는 과정을 통해 parent 배열을 최신화해주는 것을 통해 해결할 수 있었다.