Union - Find Alforithm ( SWEA 7465 . 창용 마을 무리의 개수)

● 유니온 파인드
여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프(집합)에 속해있는지 확인하거나 다른 집합인지 구별할 때 사용되는 알고리즘이다.

● 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

● 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Solution
{
     static int [] arr;
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
         
        for(int i = 1 ; i <= T; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
             
            arr = new int [N+1];
             
            for(int j=1; j<N+1;j++) {
                arr[j]=j;
            }
             
             
            for(int k=0; k<M;k++) {
                st=new StringTokenizer(br.readLine()," ");
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                unionParent(from,to);
            }
             
             
            int count = 0 ;
            for(int k =1; k<N+1;k++) {
                if(arr[k]==k) {
                    count++;
                }
            }
 
            sb.append("#").append(i).append(" ").append(count).append("\n");
        }
        System.out.println(sb.toString());
    }
    public static void unionParent(int from , int to) {
        int x = getParent(from);
        int y = getParent(to);
         
        if(x>y) {
            arr[x]=y;
        }else {
            arr[y]=x;
        }
    }
     
     
    public static int getParent(int A) {
        if(arr[A]==A) {
            return A;
        }
        return getParent(arr[A]);
    }
}

● DFS 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Solution
{
    static ArrayList<Integer> [] arr;
    static boolean [] visited;
 
    static void dfs(int cur) {
        visited[cur]= true;
         
        for(int i= 0 ; i < arr[cur].size(); i++) {
            if(visited[arr[cur].get(i)]) {
                continue;
            }
            dfs(arr[cur].get(i));
        }
         
    }
     
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
         
        int T = Integer.parseInt(br.readLine());
         
        for(int i =1; i<=T; i++) {
            st= new StringTokenizer(br.readLine()," ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
 
            arr = new ArrayList [N+1];
            visited = new boolean[N+1];
            for(int j=1; j<= N; j++) {
                arr[j] = new ArrayList<Integer>();
            }
             
            for(int j =0; j<M; j++) {
                st = new StringTokenizer(br.readLine()," ");
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                arr[from].add(to);
                arr[to].add(from);
                 
            }
            int count =0;
            for(int j = 1; j <= N; j++) {
                if(visited[j]) continue;
                dfs(j);
                count++;
            }
             
            sb.append("#").append(i).append(" ").append(count).append("\n");
        }
         
        System.out.println(sb.toString());
    }
}