백준 11724. 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

다시 푼 문제, 이전 글: tose33.tistory.com/4

 

정점 1에 대해 dfs(1)을 수행한다면, 정점 1에 이어진 모든 정점을 방문할 것이다. 

즉 dfs를 정점1에 대해 수행했는데 아직 방문하지 않은 정점이 남아있다면, 그 정점은 정점1과 이어지지 않은 정점이므로,

새로운 dfs 탐색을 시작할때마다 카운트를 증가시키면 그 카운트가 연결 요소의 개수이다.

 

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

vector<int> edge[1001];
bool mark[1001];

void dfs(int n) {
    if(mark[n]) return;
    mark[n] = true;
    //cout << n << ' ';

    for(int x : edge[n]) dfs(x);
}

int main() {
    int N, M; // 정점, 간선
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;

        edge[u].push_back(v);
        edge[v].push_back(u);
    }
/*
    for(int i = 0; i <= M; i++) {
        cout << i << ": ";
        for(int x : edge[i]) cout << x << ' ';
        cout << endl;
    } cout << endl;
*/

    int cnt = 0;
    for(int i = 1; i <= N; i++) {
        if(!mark[i]) { // 방문 안한 정점에대해 dfs 실행 
            dfs(i);
            cnt++;
        }
    }

    cout << cnt;
}

 

bfs로 풀어도 똑같다.