boj1717

문제 풀이

초기 n+1 개 집합이 있음
ex) 7 0,1,2,3,4,5,6,7

합칩함 연산과 두 원소가 같은 집합에 포함되어 있는지 확인하는 프로그램 만들기

1) 입력 n , m 연산수
2) 연산이 0 이면 집합에 뒤 두수를 합침
- 노드 두개가 들어오면 노드가 더 작은 것으로 연결
(1,3) 부모는 1
3) 연산이 1 이면 연결된 집합에서 들어오는 노드 루트 노드 찾음
루트노드가 같다면 서로 같은 노드

즉 최고 노드 루트를 찾아 해당 노드랑 해당 노드를 이어 주면 된다
[0,1,2,3,4,5,6,7]
0 1 3
[0,1,2,1,4,5,6,7]
1 이 3보다 작기 때문에
0 7 6
[0,1,2,1,4,5,6,6]
6이 7 보다 작기 때문에
0 3 7

find(3) 1
find(7) 6
[0,1,2,1,4,5,1,6]
이러면 13 76 이 연결 된거다

이처럼 find는 최고 루트를 찾는다.

문제 풀이

public class boj1717 {
   private static int[] arr;
   public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;
       st = new StringTokenizer(br.readLine());

       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());
       arr = new int[n+1];

       for(int i=0; i<=n; i++){ // n+1 까지 처음 합 집합 공간은 0으로 있음
           arr[i] = i;
       }
       StringBuilder sb = new StringBuilder();

       for(int i=0; i<m; i++) { // 연산 수

           st = new StringTokenizer(br.readLine());
           int cal = Integer.parseInt(st.nextToken()); // 연산
           int one = Integer.parseInt(st.nextToken()); // 첫 집합수
           int two = Integer.parseInt(st.nextToken()); //두번째 집합수

           switch (cal){
               case 0: // 합침
                   union(one, two);
                   break;
               case 1:
                   int first = find(one);
                   int sec = find(two);
                   if(first == sec){
                       sb.append("YES");
                       sb.append("\n");
                   }else {
                       sb.append("NO");
                       sb.append("\n");
                   }
           }
       }
       System.out.println(sb);
   }

   private static void union(int one, int two){
       int first = find(one);
       int second = find(two); // 제일 루트 연결 좌표를 찾아서 더 작은 거랑 연결

       if(first!=second){
           if(first > second){
               arr[first] = second;
           }else{
               arr[second] = first;
           }
       }
   }

   private static int find(int num){
       if(arr[num] == num){ // 만약 내가 배열의 나의 위치랑 같으면 루트
           return num;
       }else{
           return arr[num] = find(arr[num]); // 아니면 해당 노드에 들어감
       }
   }
}

---

find 메서드에서 루트를 찾고 return 으로 해당 배열에 루트를넣어 주는 작업이 중요한거 같다 안그럼 시간 초가가 발생하낟