[D 4] 창용 마을 무리의 개수

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

SW Expert Academy

 

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

public class Solution {

	public static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			int N, M;
			boolean[][] graph;

			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			graph = new boolean[N + 1][N + 1];

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());

				graph[v1][v2] = true;
				graph[v2][v1] = true;
			}

			//////////////////////////////////////////////////////

			answer = 0;
			boolean[] visited = new boolean[N + 1];
			for (int i = 1; i <= N; i++) {
				if (!visited[i]) {
					answer++;
					visited[i] = true;
					dfs(graph, visited, i);
				}
			}

			sb.append("#").append(test_case).append(" ").append(answer).append("\n");

		}
		System.out.println(sb);

	}

	public static void dfs(boolean[][] graph, boolean[] visited, int index) {

		for (int i = 1; i < graph.length; i++) {
			if (graph[index][i] && !visited[i]) {
				visited[i] = true;
				dfs(graph, visited, i);
			}
		}
	}

}

그냥 모든 점에서 dfs 조지면 된다