그래프/DFS

연결 요소의 개수 (기초!)

4gats 2023. 7. 11. 22:28

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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어

www.acmicpc.net

인접 리스트로 그래프 입력 받아서

DFS 몇 번 했는지 세는 기본적인 문제

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
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
 
using namespace std;
 
static vector<vector<int>> A;
static vector<bool> visited;
 
void DFS(int v)
{
    if (visited[v])
        return;
 
    visited[v] = true;
 
    // for-each 문
    for (int i : A[v])
    {
        if (visited[i] == false)
        {
            DFS(i);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m;
    // n은 정점 개수, m은 간선 개수
    cin >> n >> m;
    A.resize(n + 1);
    visited = vector<bool>(n + 1, false);
 
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        A[u].push_back(v);
        A[v].push_back(u);
    }
 
    int ans = 0;
 
    for (int i = 1; i < n + 1; i++)
    {
        if (!visited[i])
        {
            ans++;
            DFS(i);
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 cs