백준 - 연결 요소의 개수 11724

---

문제 분석

0이아닌 숫자가 나오면 재귀를 호출하도록 했다.

재귀는 해당 숫자가 나오면 자기자신과 옆에있는 수를 0으로 바꾸고 옆에있는 수를 또 재귀를 호출했다.

그렇게 한번 끝나면 cnt를 증가시켰다.

호출했던 수를 또 호출하면 비효율 적이기에 방문여부를 체크해서 같은 수면 안돌도록 했다.

마지막으로 자기자신만 가지고 있는 수는 연결된 수 이기때문에 방문하지 않은 수를 체크해서 cnt에 넣어줬다.

 

전체 소스

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

public class Main {
	static int[][] array;
	static boolean[] visited;
	static int repeat;

	public static void bfs(int tar) {
		if (visited[tar] == false) {
			visited[tar] = true;
//System.out.println("tar: "+tar);
			int start = 0;
			for (int i = 0; i < repeat; i++) {
				int A = array[i][0];
				int B = array[i][1];
				if (A == tar) {
					array[i][0] = 0;
					start = array[i][1];
					array[i][1] = 0;
					
					bfs(start);

				}
				if (B == tar) {
					array[i][1] = 0;
					start = array[i][0];
					array[i][0] = 0;
					bfs(start);

				}
			}

			
		} else {
			return;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int max = Integer.parseInt(st.nextToken());
		repeat = Integer.parseInt(st.nextToken());
		array = new int[repeat][2];
		visited = new boolean[max + 1];

		for (int i = 0; i < repeat; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			array[i][0] = Integer.parseInt(st.nextToken());
			array[i][1] = Integer.parseInt(st.nextToken());
		}
		boolean check = true;
		int cnt = 0;
		while (check) {
			check = false;
			for (int i = 0; i < repeat; i++) {
	
				if (array[i][0] != 0) {
					check = true;
					bfs(array[i][0]);
					break;
				}
			}
			if (check == false) {
				break;
			}
			cnt++;

		}
		for(int i=1; i<=max; i++) {
			if(visited[i]==false) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}

 

---

문제

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

입력

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

출력

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

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1