[백준 코딩테스트] 11724번 연결 요소의 개수

내 풀이

연결된 최상위 노드를 구하면 된다는 생각이 들어서 유니온 파인드 알고리즘을 사용해 접근하였다.
하지만 예시로 나와있는 두번째 입력의 결과 값이 자꾸 2로 나와서 어떻게 해결해야하는지에 대한 고민이 많았다.

노드 2와 3은 나중에 연결되기 때문에 노드 6은 갱신되지 않은 문제가 발생한다.

ArrayList<Integer> arr = new ArrayList<>();

for(int i=1; i<=n; i++){
	if(!arr.contains(parent[i])){
		arr.add(parent[i]);
    }
}

System.out.println(arr.size());

처음에는 ArrayList를 사용해 해당 배열에 포함되지 않은 값이라면 추가해준 뒤 배열의 크기를 출력해주었는데 중간에 연결된 노드의 값이 갱신되지 않아 다른 결과값이 출력되었다.
갱신되지 않은 경우를 고려해주기 위해 HashSet을 사용해 다시 각 노드의 루트를 찾아주었다.

// 연결 요소 찾기
HashSet<Integer> connected = new HashSet<>();
for (int i = 1; i <= n; i++) {
	connected.add(find(i)); // 각 노드의 루트 추가
}

내 코드

public class Main {
    static int n, m;
    static int[] parent;
    static boolean union(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y) return false;
        if(x < y) parent[y]=x;
        else parent[x] = y;

        return true;
    }

    static int find(int x){
        if(parent[x] == x) return x;
        return parent[x] = find(parent[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=1; i<=n; i++){
            parent[i] = i;
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union(a, b);
        }

        // 연결 요소 찾기
        HashSet<Integer> connected = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            connected.add(find(i)); // 각 노드의 루트 추가
        }

        // 연결 요소 개수 출력
        System.out.println(connected.size());

    }
}