백준 11724번 - 연결 요소의 개수(DFS)

 

위 예제 입력 1 을 예로 보면 1, 2, 5 끼리 서로 연결되어 있고 3,4,6  끼리 서로 연결되어 있어 출력은 2가 나온다.

 

위 문제와 비슷한 문제

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

 

▶코드

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

public class Main{
    static int edge[][];
    static boolean visited[];
    static int N, M;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        edge = new int[N+1][N+1];
        visited = new boolean[N+1];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edge[u][v] = edge[v][u] = 1;
        }
        for(int i=1;i<=N;i++){
            if(!visited[i]){
                dfs(i);
                count++;
            }
        }

        System.out.println(count);
    }
    public static void dfs(int start){
        visited[start] = true;
        for(int i=1;i<=N;i++){
            if(!visited[i] && edge[start][i]==1){
                dfs(i);
            }
        }
    }
}