[BOJ]2606ウイルス(Java)


に答える


隣接する頂点の個数をグラフィックナビゲーション(DFS)で取得する問題.
隣接マトリクスをブールとして宣言
ナビゲーションのインデックス値がtrueで、アクセスする配列がfalseの場合、結果値cntをナビゲートして増加します.

コード#コード#

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

public class Main{
	static boolean[][] arr;
	static boolean[] visited;
	static int N, cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new boolean[N+1][N+1];
		visited = new boolean[N+1];
		cnt = 0;
		int M = Integer.parseInt(br.readLine());
		for(int i =0 ; i < M ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			arr[from][to] = true;
			arr[to][from] = true;
		}
		dfs(1);
		System.out.println(cnt);
	}
	
	public static void dfs(int start) {
		visited[start] = true;
		for(int i = 1 ; i <= N ; i++) {
			if(arr[start][i] && !visited[i]) {
				dfs(i);
				cnt++;
			}
		}
	}
}