n7465_창용 마을 무리의 개수

이전에 사용한 union-find 코드와 완전 동일

여기서는 그룹의 개수가 몇개인지가 핵심 구현 부분이였다. 즉, 대표자의 개수를 알아내는것 !

package com.swea.w0824.n7465_창용마을무리의개수;

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

public class Solution {
	
	static int N;
	static int [] parents;
	
	static void make() {
		for(int i=1; i<=N;i++) {
			parents[i] = i;
		}
	}
	
	static int find(int a) {
		if(a==parents[a]) return a;
		
		return parents[a] = find(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		parents[bRoot] = aRoot;
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		for(int t = 1; t<= T; t++) {
			sb.append("#"+t+" ");
			Set<Integer> root = new HashSet<>();
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());	//사람 수 //정점 수
			int M = Integer.parseInt(st.nextToken());	//서로 알고 있는 사람의 관계 수 // 간선 수
		
			parents = new int[N+1];	
			
			make();	//각 원소들의 집합 만들기
			
			for(int m = 0; m < M; m++) {	//간선 수만큼 입력, 입력값끼리 합치기
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(find(a) != find(b)) {
					union(a,b);
				}
			}
			
			for(int n = 1; n <= N; n++) {	//정점들의 root를 set에 넣기 // 중복제거
				int X = find(n);
				root.add(X);
			}
			sb.append(root.size()+"\n");
			
		}
		System.out.println(sb);
		
	}
}