BOJ2606 바이러스

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

2606번: 바이러스

 

 

 

import java.util.*;
import java.io.*;
public class Main
{
    static List<Integer>[] graph;
    static boolean[] visited;

    
    public static int bfs(int start){
        int count = 0;
        Queue<Integer> q = new LinkedList();
        q.add(start);
        while(q.size()>0){
            int node = q.poll();
            if(visited[node]) continue;
            visited[node] = true;
            count++;
            Collections.sort(graph[node]);
            for(int n: graph[node]){
                if(!visited[n]) q.add(n);
            }    
        }
        return count;
    }
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());

	    visited = new boolean[n+1];
	    Arrays.fill(visited,false);
	    graph = new List[n+1];	
	    for(int i=0; i<n+1;i++){
	        graph[i] = new ArrayList<Integer>();
	    }
	    
	   
		for(int i = 0; i<m; i++){
		    String[] temp = br.readLine().split(" ");
		    int start = Integer.parseInt(temp[0]);
		    int end = Integer.parseInt(temp[1]);
		    graph[start].add(end);
		    graph[end].add(start);
		}

        
        System.out.println(bfs(1)-1);

		

		
	}
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int v, e;
    static int[][] graph;
    static boolean[] visited;
    static int cnt = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        graph = new int[v + 1][v + 1];
        visited = new boolean[v + 1];

        for (int i = 0; i < e; i++) {
            int src = sc.nextInt();
            int dst = sc.nextInt();
            graph[src][dst] = 1;
            graph[dst][src] = 1;
        }

//        dfs(1);
        bfs(1);
        System.out.println(cnt - 1);
    }

    public static void dfs(int node) {
        visited[node] = true;
        cnt++;
        for (int i = 1; i <= v; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
    static Queue<Integer> q = new LinkedList<>();
    public static void bfs(int node) {
        q.add(node);
        visited[node] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;
            for (int i = 1; i <= v; i++) {
                if (graph[now][i] == 1 && !visited[i]) {
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}