연결요소의 개수

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

간선으로 서로 도달할 수 있는 정점들의 묶음이 연결 요소다. 아직 방문하지 않은 정점에서 탐색을 시작하면 새로운 묶음을 발견한 것이다. 그 정점에서 도달할 수 있는 모든 정점을 방문 처리하고 개수를 한 번만 늘린다. 다음 미방문 정점이 나오기 전까지는 같은 묶음의 정점들이므로 다시 세지 않는다.

첫 예제에서는 1에서 시작한 BFS가 2와 5까지 방문한다. 다음 미방문 정점 3에서 시작하면 4와 6을 방문한다. 두 번 탐색을 시작했으므로 답은 2다. 간선이 하나도 없으면 각 정점이 혼자 한 요소를 이루어 답은 N이다. 사이클 1-2-5-1이 있어도 방문 배열 때문에 같은 정점을 무한히 돌지 않는다.

첫 예제에서 바깥 반복문이 무엇을 하는지 단계별로 보면 다음과 같다. BFS가 끝났을 때의 방문 집합을 기록했다.

검사한 시작 정점	이미 방문했나?	BFS 후 방문 집합	요소 수
1	아니오	`{1,2,5}`	1
2	예	`{1,2,5}`	1
3	아니오	`{1,2,3,4,5,6}`	2
4, 5, 6	예	변함없음	2

두 번째 예제에는 5-4 간선이 추가되어 앞의 두 묶음이 연결된다. 1에서 시작한 첫 BFS가 3, 4, 6까지 모두 도달하므로 이후에는 탐색을 새로 시작하지 않고 답이 1이 된다. 이런 식으로 BFS를 시작한 횟수와 연결 요소의 수가 일치한다.

무방향 간선은 인접 리스트의 양쪽에 모두 기록한다. BFS는 정점을 큐에 넣을 때 방문 처리해야 같은 정점이 여러 이웃에게 중복 삽입되지 않는다. 정점 N개와 간선 M개를 한 번씩 살피므로 시간 O(N+M), 인접 리스트·방문 배열·큐 공간 O(N+M)이다. 제출용 코드는 공개 클래스 이름을 Main으로 맞춘다.

bfs의 큐에는 발견됐지만 아직 이웃을 검사하지 않은 정점이 있다. check[v]=true를 먼저 기록하고 큐에 넣으므로 한 정점은 최대 한 번만 큐에 들어간다. 꺼낸 정점의 모든 이웃을 살피는 과정이 끝나면 그 정점과 직접 연결된 길도 빠짐없이 검사된다. 바깥 반복문은 1부터 N까지 돌기 때문에 고립 정점도 누락되지 않는다. 간선 하나는 양쪽 리스트에 저장되어 최대 두 번 검사되지만 상수배이므로 O(N+M)이다.

소스코드

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 11724 연결요소
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer first = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(first.nextToken());
        int m = Integer.parseInt(first.nextToken());

        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer edge = new StringTokenizer(in.readLine());
            int u = Integer.parseInt(edge.nextToken());
            int v = Integer.parseInt(edge.nextToken());
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        boolean[] check = new boolean[n+1];
        int cnt = 0;
        for (int i = 1 ; i <= n; i ++) {
            if(!check[i]) {
                bfs(adjList, check, i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void bfs(List<List<Integer>> adjList, boolean[] check, int v) {
        Queue<Integer> queue = new ArrayDeque<>();
        check[v] = true;
        queue.offer(v);
        while (!queue.isEmpty()) {
            int dequeue = queue.poll();
            for (int vertex : adjList.get(dequeue)) {
                if (!check[vertex]) {
                    check[vertex] = true;
                    queue.offer(vertex);
                }
            }
        }
    }
}