https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

---

문제 설명

창용 마을에는 N명의 사람이 살고 있다.

사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.

두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.

두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,

이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.

창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는

두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.

이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다.

같은 관계는 반복해서 주어지지 않는다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

무리의 개수를 출력한다.

---

풀이

package D4;

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

/* 서로소 집합 (유니온파인드) 문제
 * 배열로 서로소 집합을 구현해내면 됨
 * */
public class S7465_창용마을무리의개수 {
	static int[] disjoint;
	static int N, M;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());

		for (int t = 1; t <= TC; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 사람수
			makeSet(); // 서로소집합 생성
			M = Integer.parseInt(st.nextToken());
			for (int m = 0; m < M; m++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				union(a, b);
			}
//			System.out.println(Arrays.toString(disjoint));
			int res = 0;
			for (int i = 1; i <= N; i++) {
				if(i==disjoint[i])
					res++;
			}
			System.out.printf("#%d %d\n", t, res);
		}
	}

	static void makeSet() {
		disjoint = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			disjoint[i] = i;
		}
	}

	static int find(int i) {
		if (i == disjoint[i])
			return i;
		else
			return disjoint[i] = find(disjoint[i]);
	}

	static boolean union(int n1, int n2) {
		int p1 = find(n1);
		int p2 = find(n2);

		if (p1 == p2) // 알고보니 둘이 같은소속!!
			return false; // 그럼 안됨
		disjoint[p1] = p2;
		return true;
	}
}