[백준 11724] 연결 요소의 개수(Java)

반응형

1. 문제

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

2. 풀이

• 백준 1012 유기농 배추와 유사하게 풀이하였다.
• 연결된 노드는 true로 처리하여 카운트되지 않게 하였다.
• 정점과 정점이 이어져있는 것을 확인하기 위해 1로 배열에 표기해주었다.

3. 코드

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

public class Main {

	static int N,M;
	static int[][] map;
	static boolean[] visited;
	static int result;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new StringReader(src));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];
		visited = new boolean[N+1];
		
		for(int i =0; i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b]=map[b][a]=1;
		}
		for(int i =1; i<=N;i++) {
			if(!visited[i])
				result++;
			dfs(i);
		}
		System.out.println(result);
		
	}
	static void dfs(int start) {
		visited[start] = true;
		for(int i =1; i<=N;i++) {
			if(map[start][i]==1 && !visited[i]) {
				dfs(i);
			}
		}
	}
	



	static String src = 
			"6 5\r\n" + 
			"1 2\r\n" + 
			"2 5\r\n" + 
			"5 1\r\n" + 
			"3 4\r\n" + 
			"4 6";
}