연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

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

public class Main {

	static int[][] graph;
	static boolean visited[];
	static int N;
	static int M;

	public static void dfs(int i) { // DFS
		visited[i] = true;

		for (int j = 1; j <= N; j++) {
			if (graph[i][j] == 1 && visited[j] == false) {
				dfs(j);
			}
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		graph = new int[N + 1][N + 1];
		visited = new boolean[N + 1];
		int a, b;

		for (int i = 1; i <= M; i++) {
			a = sc.nextInt();
			b = sc.nextInt();

			graph[a][b] = graph[b][a] = 1;
		}

		for (int j = 1; j <= N; j++) {
			visited[j] = false;
		}

		int cnt = 0;	// 연결 요소 개수

		for (int k = 1; k <= N; k++) {
			if (visited[k] == false) {	// 방문한적이 없으면 새로운 연결 요소
				dfs(k);
				cnt++;
			}
		}

		System.out.println(cnt);
	}
}

 

문제출처

https://www.acmicpc.net/problem/11724