[백준/C++][연결 요소의 개수(11724번)]

문제

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

11724번: 연결 요소의 개수

문제 해결

1. 인접 리스트로 정점들을 저장한다.

2. 1~N까지 방문하지 않은 노드들을 DFS 한다.

3. 방문할 때 마다 cnt를 해준다.

 

코드

#include <iostream>
#include <vector>
#define Max 1001
using namespace std;
int N,M,cnt = 0;
vector <int> adj[Max];
bool visit[Max] = {false};
bool visited[Max] = {false};
void DFS(int node){
    visit[node] = true;
    visited[node] = true;
    for(int i = 0;i<adj[node].size();i++){
        int next_node = adj[node][i];
        if(visit[next_node]){continue;}
        else{DFS(next_node);}
    }
}
int main(void){
    cin >> N >> M;
    for(int i = 0;i<M;i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1;i<=N;i++){
        if(visited[i]){continue;}
        else{
            visited[i] = true;
            DFS(i);
            cnt++;
        }
    }
    cout << cnt;
}