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

Posted on | In |

문제 보러가기

제한사항

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

첫번째 생각

하나의 묶음을 계산해내는 문제.

disjoint-set 즉, 유니온파인드 개념을 사용해서 풀이하면 된다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Scanner;

public class Solution {
	static int[] parent;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			parent = new int[N+1];
			boolean[] ans = new boolean[N+1]; 
			for(int i=1; i<N+1; i++) 
				parent[i] = i;
			for(int i=0; i<M; i++) {
				int A = sc.nextInt();
				int B = sc.nextInt();
				if ( find(A) != find(B) ) {
					union(A,B);
				}
			}
			int cnt = 0;
			for(int i=1; i<N+1; i++) {
				int A = find(i);
				if ( !ans[A] ) { 
					cnt++;
				}
				ans[A] = true;
			}
			
			System.out.println("#"+tc+" "+cnt);
		}
	}
	
	static int find(int n) {
		if ( n == parent[n] ) {
			return n;
		} else {
			return parent[n] = find(parent[n]);
		}
	}
	
	static void union(int n1,int n2) {
		int p1 = find(n1);
		int p2 = find(n2);
		
		if ( p1 != p2 ) { 
			parent[p2] = p1; 
		}
	}
}