Union find

public static boolean union(int x, int y) {
	x = find(x); //x의 부모노드 찾기
	y = find(y); //y의 부모노드 찾기
    
	// 이미 같은 그래프에 속해있을 때 false 반환
	if(x == y) return false;
	
	if(x <= y) parent[y] = x;
	else parent[x] = y;
	return true;
}

public static int find(int x) {
	if(parent[x] == x) return x;
	return find(parent[x]);
}
Java
복사

import java.io.*;
import java.util.*;

class Solution {
    
    static Integer[] parent;
    
    public int solution(int n, int[][] computers) {
        
        parent = new Integer[n];
        
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                
                if(i == j) continue;
                
                if(computers[i][j] == 1) {
                    union(i, j);
                    System.out.println(Arrays.toString(parent));
                }
            }
        }
        
        // 갱신 안됐을수도 있으니 한번더
        for(int i = 0; i < n; i++) {
            parent[i] = find(i);
        }
        
        
        Set<Integer> set = new HashSet<>(Arrays.asList(parent));
        
        return set.size();
    }
    
    public void union(int a, int b) {
        
        a = find(a);
        b = find(b);
        
        if(a <= b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
    
    public int find(int a) {
        if(a == parent[a]) return a;
        
        return parent[a] = find(parent[a]);
    }
}
Java
복사