[C++][Beakjoon] 11724번 연결요소

[문제]

11724번: 연결 요소의 개수

---

[풀이]

벡터를 활용한 인접리스트와 DFS로 품~!

 

*동적할당부분 기억하깅...

vector<int> *graph = new vector<int>[vertexNum + 1]; //인접리스트 동적할당
bool *visited = new bool[vertexNum + 1];

 

[풀이 코드]

#include <iostream>
#include <vector>
using namespace std;

void dfs(int vertex, vector<int> graph[], bool *visited);

int main() {
    int vertexNum, edgeNum, u, v;
    cin >> vertexNum >> edgeNum;

    vector<int> *graph = new vector<int>[vertexNum + 1]; //인접리스트 동적할당
    bool *visited = new bool[vertexNum + 1];

    for (int i = 0; i < edgeNum; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 0; i < vertexNum; i++) visited[i] = false;

    int count = 0;
    for (int i = 1; i <= vertexNum; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited);
            count++;
        }
    }
    cout << count;

    delete[] visited;
    return 0;
}

void dfs(int vertex, vector<int> graph[], bool *visited) {
    visited[vertex] = true;
    for (int i = 0; i < graph[vertex].size(); i++) {
        if (!visited[graph[vertex][i]]) dfs(graph[vertex][i], graph, visited);
    }
}