[백준 2606번] 바이러스

문제 링크: 2606번 바이러스

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

 

서로 연결된 노드들의 집합 개수를 구하는 문제이다. 1번 컴퓨터와 네트워크 상에서 직접 연결된 컴퓨터의 수를 구하면 되므로, 모든 탐색을 끝마친 후 visit 배열의 true 개수를 모두 세고, 1번 컴퓨터를 뺀 값을 출력한다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int computers = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        int pairs = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        ArrayList<Integer>[] graph = new ArrayList[computers];
        boolean[] visited = new boolean[computers];

        for (int i = 0; i < computers; i++)
            graph[i] = new ArrayList<Integer>();

        for (int i = 0; i < pairs; i++) {
            int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = temp[0] - 1;
            int end = temp[1] - 1;
            graph[start].add(end);
            graph[end].add(start);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int connected : graph[cur]) {
                if (!visited[connected]) {
                    visited[connected] = true;
                    queue.offer(connected);
                }
            }
        }

        int cnt = 0;
        for (boolean item : visited)
            if (item)
                cnt++;

        System.out.println(cnt-1);
    }
}