백준 11724 연결 요소의 개수 [C++]

작성일 | In |

Problem : 연결 요소의 개수

유형 : 그래프 탐색

문제 해석

  • 무방향 그래프에서 연결요소의 개수를 구한다.
    • 연결된 요소의 집합이 몇개인지를 구한다.

해결 전략

  • DFS 를 통해 연결요소 집합의 개수를 구한다.

설계, 구현

  • 인접 리스트를 이용해 그래프간의 연결 관계를 설정한다.
  • 재귀적으로 DFS로 연결된 그래프 관계를 확인한다.
  • 새로운 집합이 발견될때마다 경우의 수를 1씩 증가시킨다.

주의할 점

  • 무방향 그래프이다. 즉, 양방향 그래프이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1002;

vector<int> node[MAX];
bool visited[MAX];
int n, m;

void dfs(int curNode) {
    for (const int& nextNode : node[curNode]) {
        if (visited[nextNode]) continue;
        visited[nextNode] = true;
        dfs(nextNode);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }

    int answer = 0;

    for (int i = 1; i <= n; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        answer++;
        dfs(i);
    }
    cout << answer << "\n";
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 없음