Android in A..Z - DFS

개념

그래프를 탐색할 때 해당 분기를 먼저 탐색하는 방법

---

작동원리

1. 갈 수 있는 정점이 있으면 들어간다.

2. 갈 수 있는 정점이 없으면 가장 가까운 분기로 돌아가서 다른 방향으로 들어간다.

---

시간복잡도

O(V + E)

---

문제

11724 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> graph;

vector<bool> isVisited;
void dfs(int index) {
    for (auto &next : graph[index]) {
        if (!isVisited[next]) {
            isVisited[next] = true;
            dfs(next);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;

    graph.resize(n + 1);
    while (m--) {
        int u, v;
        cin >> u >> v;

        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }

    int ans = 0;
    isVisited.resize(n + 1, false);
    for (int i = 1;i <= n;++i) {
        if (!isVisited[i]) {
            ans++;
            dfs(i);
        }
    }

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