[BOJ] 9372 상근이의 여행

문제

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

풀이

- BFS 활용 풀이

import java.io.*;
import java.util.*;


public class Main {
	static boolean[][] graph;
	static boolean[] visited;
	static int result;
	
	static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		visited[1] = true;
		while(!queue.isEmpty()) {
			result++;
			int tmp = queue.poll();
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i] && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}
    public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int T,N,M;
    	T = Integer.parseInt(br.readLine());
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	M = Integer.parseInt(st.nextToken());
        	graph = new boolean[N+1][N+1];
        	visited = new boolean[N+1];
        	result = 0;
        	for(int j=0;j<M;j++) {
        		st = new StringTokenizer(br.readLine());
            	int from = Integer.parseInt(st.nextToken());
            	int to = Integer.parseInt(st.nextToken());
            	graph[from][to] = graph[to][from] = true;
        	}
        	bfs(N);
        	sb.append(result-1+"\n");
    	}
    	
    	System.out.println(sb);
    }
}