SWEA7465 창용 마을 무리의 개수

·2022년 4월 27일
0

SWEA 알고리즘

목록 보기
25/29

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

public class Solution {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N;
	static int[] parents;
	static boolean[] isSelected;

	public static void makeSet() {
		parents = new int[N];
		// 자신의 부모노드를 자신의 값으로 세팅.
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}

	}

	public static int findSet(int a) {
		if (a == parents[a])
			return a;
		return parents[a] = findSet(parents[a]);
	}

	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false;

		parents[bRoot] = aRoot;
		return true;
	}

	public static void main(String[] args) throws IOException {
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()) + 1;
			int M = Integer.parseInt(st.nextToken());
			makeSet();
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			isSelected = new boolean[N];
			int answer = 0;
			for(int i = 0; i < N; i++) {
				isSelected[findSet(i)] = true;
			}
			for(int i = 1; i < N; i++) {
				if(isSelected[i]) answer++;
			}
			
			bw.append("#" + tc + " " + answer + "\n");
		}
		bw.flush();
	}
}
profile
SSAFY 7기

0개의 댓글