[BOJ] 2606번 바이러스

문제

www.acmicpc.net/problem/2606

2606번: 바이러스

 

풀이

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

public class Main {
	static int cnt=0;
	public static void round_graph(int size,boolean[][] graph, boolean[] visited) {
		dfs(graph,visited,1,size);
	}
	public static void dfs(boolean[][] graph, boolean[] visited,int start, int size) {
		visited[start] = true;//정점 방문 체크
		for(int i=1;i<=size;i++) {
			if(graph[start][i] && !visited[i]) {
				//간선 존재 여부와 반대편 정점 방문 여부를 동시에 확인
				cnt++;
				dfs(graph,visited,i,size);
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cps = Integer.parseInt(br.readLine());
		int pairs = Integer.parseInt(br.readLine());
		boolean[][] graph = new boolean[cps+1][cps+1];//그래프 배열
		boolean[] visited = new boolean[cps+1];//방문 여부 확인 배열
		
		//그래프 생성
		for(int i=0;i<pairs;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken()); 
			graph[from][to] = graph[to][from] = true;
		}
		
		//계산
		round_graph(cps,graph,visited);
		
		//출력
		System.out.println(cnt);
	}

}