[BOJ 11724] 연결 요소의 개수

난이도

매겨진 난이도: Silver II (Standard)

체감 난이도: Silver II (±0)

 

태그

• Depth First Search (깊이 우선 탐색)
• Connected Component (연결 요소)

 

풀이

1. 하나의 연결 요소를 구하는 방법은?

방향 없는 그래프에서 연결 요소를 구하는 방법은, 어떤 정점에서 출발해서 DFS를 돌린 뒤, 방문한 정점들을 모으면 됩니다.

 

2. 그럼 연결 요소의 개수는?

(1번 질문의 답)을, 아직까지 방문하지 않은 정점 하나를 찾은 뒤 이에 대해 돌려주면 됩니다.

한 번 반복에 새로운 연결 요소 하나를 찾게 되므로, 문제의 답은 반복의 횟수가 됩니다.

 

3. 시간복잡도는?

(맨 아랫줄만 읽으셔도 됩니다.)

 

DFS 함수의 호출 횟수는, 각 정점별로 1번씩 호출되므로 합해서 \( O(N) \)회가 됩니다.

 

전체적인 시간복잡도는, 아래와 같이 계산할 수 있습니다.

\( \sum\limits_{v=1}^{N} \) (dfs(v)의 호출 횟수) × (dfs(v)의 시간복잡도)

dfs(v)는 각 정점에 대해 1번씩 호출되고, dfs(v)의 시간 복잡도는 \( O(\text{deg}(v)) \)이므로, 결론적으로

\( \sum\limits_{v=1}^{N} 1 \times O(\text{deg}(v)) = O(M) \)이 됩니다.

 

즉, 우리가 알던 DFS 시간복잡도인 \( O(V+E) \)임을 알 수 있습니다.

 

코드

vector<int> adj[1020];
 
bool chk[1020];
void dfs(int now){
    chk[now] = 1;
    for (int nxt : adj[now]){
        if (chk[nxt]){ continue; }
        dfs(nxt);
    }
}
 
void Main(){
    int n, m; cin >> n >> m;
    while (m--){
        int v, w; cin >> v >> w;
        adj[v].push_back(w); adj[w].push_back(v);
    }
    int ans = 0;
    for (int v = 1; v <= n; v++){
        if (chk[v]){ continue; }
        dfs(v); ans += 1;
    }
    cout << ans;
}