[백준/C++]#11724 - 연결 요소의 개수

풀이

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

vector<int> a[1001];	// 저장공간 정의
bool check[1001];

void dfs(int node) {
    check[node] = true;		// 왔다감 체크
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {		// 체크 확인
            dfs(next);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    int i, count = 0;
    for (int i=1; i<=n; i++) {
    	if(check[i] == false) {		// 가본적 없는 노드일 때 count
    		count++;
    		dfs(i);
    	}
    }
    cout << count;
    return 0;
}

풀이

 

 

이 문제를 푸는 방법은, 자료구조 및 알고리즘 수업에서 배운 적이 있다.

사실 dfs, bfs 무엇을 써도 상관 없다.

 

연결성분을 세기 위해 count 변수를 설정한다.

기존에 만든 탐색 방법은 연결되지 않은 정점에는 이동하지 못한다.

따라서 모든 정점에 접근하기 위해 정점 수만큼 반복한다.

반복문 안에서 check[i]==false 이면 방문(탐색)을 하면 된다.

한번 탐색을 거치면, 연결된 정점은 모두 true 값을 가지게 되므로 이를 통해 연결성분의 수를 구할 수 있다.

 

---

+a

다른풀이(BFS를 사용한 경우 )

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

vector<int> a[1001];	// 저장공간 정의
bool check[1001];

void dfs(int node) {
    check[node] = true;		// 왔다감 체크
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {		// 체크 확인
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    check[start] = true;
    q.push(start);
    while (!q.empty()) {	// queue가 빌 때까지
        int node = q.front();
        q.pop();
        for (int i=0; i<a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {		// 체크 확인
                check[next] = true;		// 왔다감 체크
                q.push(next);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    int i, count = 0;
    for (int i=1; i<=n; i++) {
    	if(check[i] == false) {		// 가본적 없는 노드일 때 count
    		count++;
    		bfs(i);
    	}
    }
    cout << count;
    return 0;
}