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

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

 

문제

 

설명

 

서로소 집합을 응용해서 푸는 문제입니다. 완성된 무리의 갯수를 센다는 것은 union을 통해 만들어진 무리들의 대표자 수를 세는 것과 동일한 개념이기 때문입니다.

 

다만, 어떤 무리에 속해있는 사람의 수가 총 한 명이라도 역시 하나의 무리로 친다는 점을 유의해야 합니다!!

 

 

 

코드

import java.util.ArrayList;
import java.util.Scanner;

public class SWEA7465_Village {

	static int N, M;
	static int[] parents;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); //테케 수

		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt(); //마을에 사는 사람들 수
			M = sc.nextInt(); //서로를 알고 있는 사람의 관계 수

			parents = new int[N+1]; //1번부터 시작
			make();

			for(int i=0; i<M; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				union(a, b);
			}
			ArrayList<Integer> list = new ArrayList<>();
			for(int i=1; i<=N; i++) {
				if(list.contains(find(i))) {
					continue;
				} 
				list.add(find(i));
			}
			System.out.println("#" + tc + " " + list.size());
		}
	}

	private static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);

		if(aRoot==bRoot)
			return;
		parents[bRoot]=aRoot;
	}

	private static int find(int a) {
		if(parents[a]==a)
			return a;
		return parents[a] = find(parents[a]);
	}

	private static void make() {
		for(int i=1; i<=N; i++)
			parents[i]=i;
	}
}