그래프 문제(bfs,dfs) #11724: 연결 요소의 개수 [JAVA]

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

11724번: 연결 요소의 개수

 

 

---

 

 

 

문제 접근

 

 

 

 

정점 1~N까지 dfs나 bfs를 호출하여 그래프를 순회하면서 

방문한 vertex를 체크하고

방문하지 않았던 노드들에 대해서 순회할 때마다 cnt를 증가시켜 연결 요소의 개수를 구한다.

 

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

 

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

public class Main {

	static int vertex;
	static int edge;
	static boolean[] visited;
	static int[][] adj;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		vertex = Integer.parseInt(st.nextToken());
		edge = Integer.parseInt(st.nextToken());

		adj = new int[vertex + 1][vertex + 1];
		visited = new boolean[vertex + 1];

		for (int i = 0; i < edge; i++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			adj[a][b] = 1;
			adj[b][a] = 1;
		}

		int cnt = 0;
		for (int i = 1; i < vertex + 1; i++) {
			if (!visited[i]) {
				dfs(i);
				cnt++;
			}
		}

		System.out.println(cnt);
	}

	static void dfs(int v) {

		visited[v] = true;

		for (int i = 1; i < vertex + 1; i++) {
			if (!visited[i] && adj[v][i] == 1) {
				dfs(i);
			}
		}
	}

}