[SWEA] 7465. 창용마을 무리의 개수 (d4)

문제

---

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

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

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

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

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

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

[입력]

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

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

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

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

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

[출력]

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

무리의 개수를 출력한다.

입력

2
6 5
1 2
2 5
5 1
3 4
4 6
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

출력

#1 2
#2 1

풀이

---

문제 유형 : 그래프, union-find

1. 총 무리의 갯수를 N으로 초기화한다.
2. 들어오는 입력에 대해서 union 을 한다.
3. union 의 return 값이 true 라면 (무리가 하나로 합쳐짐) N-1 을 한다.
4. 최종 N을 출력한다.

코드

---

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

/*
 * cnt 를 N으로 놓고 union 할 때 마다 -1 씩해서 출력
 */

public class Solution_d4_7465_창용마을무리의개수2 {
	
	static int[] parents;
	static int N;
	
	static void makeSet() {
		parents = new int[N+1];
		
		for(int i=1; i<=N; i++)
			parents[i] = -1;
	}
	
	static int findSet(int a) {
		if(parents[a] == -1) return a;
		return parents[a] = findSet(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int pa = findSet(a);
		int pb = findSet(b);
		
		if(pa == pb) return false;
		parents[pb] = pa;
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_d4_7465.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int tc=1; tc<=T; tc++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			makeSet();
			int cnt = N;
			
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(union(a, b))
					cnt--;
			}
			
			sb.append("#").append(tc).append(" ").append(cnt).append("\n");
		}
		
		System.out.print(sb.toString());
		br.close();
	}

}