[SWEA] 7465 창용 마을 무리의 개수 - JAVA

1. 문제

SW Expert Academy

창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.
두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.
창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

---

2. 풀이

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

public class D4_7465_창용마을무리의개수X {
   static int[] people, size;
   static int count;
   public static void main(String[] args) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());

      StringBuilder sb = new StringBuilder();

      for(int tc=1;tc<=T;tc++){
         sb.append("#").append(tc).append(" ");

         StringTokenizer st = new StringTokenizer(in.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());

         count = N;

         size = new int[N+1];
         people = new int[N+1];
         for(int i=1;i<=N;i++) people[i] = i;

         for(int m=0;m<M;m++){
            st = new StringTokenizer(in.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(link(a,b)) --count;

         }

         sb.append(count).append("\n");
      }

      System.out.print(sb);
   }

   private static int find(int x){
      if(people[x]==x) return x;
      people[x] = find(people[x]);
      return people[x];
   }

   private static boolean link(int a, int b) {
      int pa = find(a);
      int pb = find(b);

      if(pa==pb) return false;

      if(size[pa]>size[pb]) people[pb] = pa;
      else if(size[pa]==size[pb]) size[pb]++;

      if(size[pb]>size[pa]) people[pa] = pb;

      return true;
   }
}

---

3. 결과

[SWEA] 3289 서로소집합 과 비슷하다.