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

1. 문제 유형 : Union-Find

2. 시간복잡도 : O(MN)

 

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

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int[] parents = new int[N+1];
			for (int i = 0; i < N+1; i++) {
				parents[i] = i;
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(in.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				union(parents, from, to);
			}
			
			int answer = 0;
			boolean[] isRoot = new boolean[N+1];
			for (int i = 1; i < N+1; i++) {
				int root = findSet(parents, i);
				if(!isRoot[root]) {
					isRoot[root] = true;
					answer++;
				}
			}
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}
	
	public static int findSet(int[] parents, int a) {
		if(parents[a] == a) return a;
		return parents[a] = findSet(parents, parents[a]);
	}
	
	public static void union(int[] parents, int a, int b) {
		int aRoot = findSet(parents, a);
		int bRoot = findSet(parents, b);
		if(aRoot == bRoot) return;
		
		parents[bRoot] = aRoot;
	}

}