(2) [C++, Java] 백준 No.11724 : 연결 요소의 개수

문제

풀이

자세한 풀이 :  https://ldgeao99.tistory.com/398

# C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr[1001]; // 인접 리스트
int check[1001];       // 중복방문을 막기위한 check 배열
void dfs(int node);    // DFS 탐색함수

int main()
{
    // cin, cout 속도 빠르게 하기
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 정점의 개수 n과 간선의 개수 m 입력받기
    int n, m;
    cin >> n >> m;

    // 연결된 두 정점들에 대한 정보를 받아서 인접리스트 생성
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        // 방향이 없는 그래프이므로 양방향에 대해서 넣어줌
        arr[u].push_back(v);
        arr[v].push_back(u);
    }

    // dfs 탐색이 진행된 횟수를 카운트 함 => 이 부분에서 사용되는 탐색을 BFS로 바꿔주면 BFS로도 가능함
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if (check[i] == false){
            dfs(i);
            ans += 1;
        }
    }

    cout << ans << "\n";
}

void dfs(int node){
    check[node] = true;
    //cout << node << " ";
    for (int i = 0; i < arr[node].size(); i++){
        if(check[arr[node][i]] == false){
            check[arr[node][i]] = true;
            dfs(arr[node][i]);
        }
    }
}

# Java

import java.util.*;

public class Main {
    public static void dfs(ArrayList<Integer>[] a, boolean[] c, int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        for (int y : a[x]) {
            if (c[y] == false) {
                dfs(a, c, y);
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        boolean[] check = new boolean[n+1];
        int ans = 0;
        for (int i=1; i<=n; i++) {
            if (check[i] == false) {
                dfs(a, check, i);
                ans += 1;
            }
        }
        System.out.println(ans);
                

    }
}