알고리즘

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

J3SUNG 2023. 3. 2. 02:15
728x90

N명의 사람들이 서로 관계가 이어져 있습니다.
이 때 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계는 하나의 무리로 판단합니다.
무리의 수를 찾는 문제입니다.

이어진 관계를 따라가서 전부 방문처리해주고 카운트를 해주었습니다.
모든 사람을 기준으로 위의 과정을 하고 카운트 된 값을 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Solution {
  public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      StringTokenizer st;
      int testcase = Integer.parseInt(br.readLine());
       
      for(int t=1; t<=testcase; ++t) {
        bw.write("#" + t + " ");
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] p = new int[n+1];
        int ans = 0;
         
        for(int i=1; i<=n; ++i) {
            p[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());
             
                int rootA = a;
                int rootB = b;
                while(rootA != p[rootA]) {
                    rootA = p[rootA];
                }
                while(rootB != p[rootB]) {
                    rootB = p[rootB];
                }
                if(rootA < rootB) {
                    p[rootA] = rootB;
                } else if (rootA > rootB) {
                    p[rootB] = rootA;                   
                }
        }
        for(int i=1; i<=n; ++i) {
            if(p[i] == i) {
                ++ans;
            }
        }
        bw.write(ans + "\n");
      }
      bw.close();
  }
}