11724. 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

그래프가 주어지고 그 그래프가 연결돼 있는지 분리돼 있는지 판단하고 

분리되어 있으면 몇 개로 분리되어 있는지 알아내는 문제. 

 

일단 그래프가 분리되있는지 하나로 돼있는지 판단해야 하는데 DFS로 (BFS로 해도 될 것 같다)

첫 번째 정점에서부터 탐색을 시작한다. 

DFS로 탐색을 시작한다면 이어져있는 모든 정점을 방문하고 돌아올 것이고 방문된 정점은 모두 true로 mark가 돼있을 것이다. 

 

그렇다면 DFS탐색을 한번 수행하고 돌아왔을 때 true로 mark 돼 있지 않은 정점이 있다면 그래프가 하나가 아닌 분리된 그래프라는 것일 것이다. 

 

간선의 양 끝점 u와 v가 다음과 같다면

1 2 

2 5

5 1

3 4

4 6

 

그래프는 다음과 같이 생겼을 것이다

DFS를 다음과 같이 돌리면

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

1 - 2 - 5 탐색하고 돌아오고

1,2는 이미 방문했으므로 3에서부터 DFS를 수행한다.

3 - 4 - 6 탐색하고 돌아오고 보니 모든 정점을 방문했다.

 

새롭게 DFS 탐색할때마다 cnt값을 증가시키면 cnt가 그래프가 분리된 개수이다. 

 

코드

import java.util.*;

public class Main {
    // 간선 정보 저장할 edge
    static ArrayList<Integer> edge[] = new ArrayList[1001];
    // 방문여부 저장할 mark
    static boolean mark[] = new boolean[1001];

    // Dept First Search
    static void dfs(int n) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(n); mark[n] = true;


        while(!s.empty()) {
            int f = s.peek();
            boolean none = true;

            for(int x : edge[f]) {
                if(mark[x] == false) {
                    s.push(x); mark[x] = true;

                    none = false;
                    break;
                }
            }
            if(none) s.pop();
        }
    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(); // 정점의 개수
        int m = s.nextInt(); // 간선의 개수
        int cnt = 0;

        // 2차원 edge 생성
        for(int i = 0; i <= n; i++) {
            edge[i] = new ArrayList<Integer>();
        }

        // 간선정보 edge에 저장
        for(int i = 0; i < m; i++) {
            int t, f;
            t = s.nextInt();
            f = s.nextInt();

            edge[f].add(t);
            edge[t].add(f);
        }

        // 방문 가능 정점 여러개일때 번호가 작은것부터 방문하므로 정렬
        for(int i = 1; i <= n; i++)
            Collections.sort(edge[i]);

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

        System.out.println(cnt);
    }

}