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

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

11724번: 연결 요소의 개수

 

---

 

메모

 

행래 교수님 강의자료에 다 나와있지롱 ㅎㅂㅎ

 

 

 

 

 

 

 

 

코드

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static boolean[] visited;
	static LinkedList<Integer>[] graph;
	static int cnt;

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bf.readLine());
		int verN = Integer.parseInt(st.nextToken());
		int edgeN = Integer.parseInt(st.nextToken());

		graph = new LinkedList[verN + 1];

		for (int i = 1; i < verN + 1; i++) {
			graph[i] = new LinkedList<>();
		}

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

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

			graph[a].add(b);
			graph[b].add(a);
		}

		visited = new boolean[verN + 1];

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

		System.out.println(cnt);
	}

	static void dfs(int v) {

		visited[v] = true;

		for (int e : graph[v]) {
			if (!visited[e]) {
				dfs(e);
			}
		}
	}

}