[백준] 민서의 응급 수술 - Java 20955

Union-Find 알고리즘

 

유니온 파인드 알고리즘을 사용하는 문제이다.

오랜만에 유니온 파인드를 사용한 것 같다.

 

이 문제는 연결을 끊거나 연결을 생성함으로 하나의 트리를 형성하는 것이다.

 

따라서, 입력받을 때 사이클이 존재한다면 해당 연결을 끊어야 하므로, 값을 증가시켜주고

만약, 연결이 끊어져있는 곳이 있다면 이어줘야 하므로 union으로 합처준 뒤 값을 증가시킨다.

 

이때, 나는 1(최소값)으로 유니온 파인드가 진행되게 했으므로, 1이 아닌 경우 이어주게 해줬다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj20955 {
    public static void main(String[] args) throws IOException {
        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());

        int[] parent = new int[N + 1];

        for(int i = 1; i <= N; i++){
            parent[i] = i;
        }

        int result = 0;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(find_parent(parent, a) != find_parent(parent, b)){
                union(parent, a, b);
            } else{
                result++;
            }
        }

        for(int i = 1; i <= N; i++){
            if(find_parent(parent, i) != find_parent(parent, 1)){
                union(parent, i, 1);
                result++;
            }
        }

        System.out.println(result);
    }

    public static int find_parent(int[] parent, int p){
        if(parent[p] == p)
            return parent[p];

        p = find_parent(parent, parent[p]);

        return p;
    }

    public static void union(int[] parent, int a, int b){
        a = find_parent(parent, a);
        b = find_parent(parent, b);

        if(a < b){
            parent[b] = parent[a];
        } else{
            parent[a] = parent[b];
        }
    }
}