π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] Q.11724 μ°κ²° μμμ κ°μ
π λ¬Έμ
https://www.acmicpc.net/problem/11724
λ°©ν₯ μλ κ·Έλνκ° μ£Όμ΄μ‘μ λ, μ°κ²° μμ (Connected Component)μ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
π μ κ·Όλ²
BOJ Q.11724 μ°κ²° μμμ κ°μ
μ°κ²° μμμ κ°μ
μ¦ λͺκ°μ μ°κ²° κ·Έλνκ° μλ μ§ μ λλ€.
κ°μ€μΉκ° μλ κ·Έλνκ° μ£Όμ΄μ§λ―λ‘ BFS / DFS λ‘ νμ΄κ° κ°λ₯ν©λλ€.
무방ν₯κ·Έλνκ° μ£Όμ΄μ§λ―λ‘ μΈμ 리μ€νΈλ₯Ό μΆκ°ν λ μμͺ½μΌλ‘ μΆκ° ν΄μ€λλ€ (u,v) (v,u) μ°κ²°
κ·Έ ν
BFS DFS νμμ ν΅ν΄ μ°κ²° κ·Έλνμ κ°μλ₯Ό ꡬν μ μμ΅λλ€.
π» μ½λ
package problem.bfsdfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main_11724 {
static int N, M, answer;
static boolean[] visit;
static List<List<Integer>> adList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner sc = new Scanner(System.in);
String input[] = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
adList = new ArrayList<>();
for(int i=0; i<N+1; i++) {
adList.add(new <Integer>ArrayList());
}
visit = new boolean[N + 1];
for (int i = 0; i < M; i++) {
String temp[] = br.readLine().split(" ");
int u = Integer.parseInt(temp[0]);
int v = Integer.parseInt(temp[1]);
adList.get(u).add(v);
adList.get(v).add(u);
}
answer = 0;
for (int i = 1; i <= N; i++) {
if (!visit[i]) {
dfs(i);
answer++;
}
}
System.out.println(answer);
br.close();
}
public static void bfs(int num){
Queue<Integer> queue = new LinkedList<>();
visit[num] = true;
queue.add(num);
while(!queue.isEmpty()){
int current = queue.poll();
for (int next : adList.get(current)) {
if(visit[next]==true){
continue;
}
visit[next]=true;
queue.add(next);
}
}
}
public static void dfs(int num){
visit[num] = true;
for(int next : adList.get(num)){
if(visit[next]){
continue;
}
dfs(next);
}
}
}
Written on October 24, 2020