[BOJ] 백준 11724 연결요소의 개수

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

 Input 

6 5

1 2

2 5

5 1

3 4

4 6

 

 Output 

2

※ 연결요소(Connected component)?　

전체 그래프(G)에서 정점과 간선이 겹치지 않는 부분 그래프를 의미합니다.

(또한, 부분 그래프의 합집한은 전체 그래프입니다.)

① 정점과 간선 정보를 인접행렬로 구현.

② BFS로 연결된 지점을 방문하여 부분 그래프의 개수를 파악합니다.

 

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        // 정점의 개수
        int N = Integer.parseInt(sc.next());
        // 간선의 개수
        int M = Integer.parseInt(sc.next());
         
        // 1~N까지 인접행렬로 표현
        int[][] arr = new int[N+1][N+1];
         
        for(int i=0; i<M; i++) {
            int x = Integer.parseInt(sc.next());
            int y = Integer.parseInt(sc.next());
             
            arr[x][y] = 1; arr[y][x] = 1;
        }
         
        // 방문 여부
        boolean[] visited = new boolean[N+1];
        Queue<Integer> queue = new LinkedList<>();
         
        int answer = 0;
        // 모든 노드에 대해서 탐색을 한다.
        // 이때, 연결되어 있는 노드들은 방문 표시를 해서 다음 탐색에서 제외시킨다.
        // 즉, BFS로 연결되어 있는 지점을 제외시켜가는 것이다.
        for(int i=1; i<=N; i++) {
            // 아직 방문하지 않았다면 BFS 탐색을 준비한다.
            if(!visited[i]) {
                queue.add(i);
                answer++;
            }
            // BFS탐색 시작
            while(!queue.isEmpty()) {
                int curNode = queue.poll();
                // 아직 방문한적이 없다면 연결되어 있는 노드를 탐색
                if(!visited[curNode]) {
                     
                    // 현재 노드는 방문한 것으로 표시!
                    visited[curNode] = true;
                     
                    // 연결되어 있는 노드 중에 아직 방문한적이 없는 노드를 queue에 삽입
                    for(int j=1; j<=N; j++) {
                        if(arr[curNode][j] == 1 && !visited[j]) {
                            queue.add(j);
                        }
                    }
                }
            }
        }
        // 정답 출력
        System.out.println(answer);
         
    }
}