[BFS] BJ11734 연결 요소의 개수

문제 출처: https://www.acmicpc.net/problem/11724

 

Solution

• BFS 한 번 하면 연결 요소 (Connected Component) 구할 수 있으므로, 그래프에서 BFS 횟수를 구하면 된다.

Point

• 그래프 탐색이 곧 연결된 모든 노드를 탐색하는 것을 의미한다.
• adjList 저장 시에는 반드시 양쪽 노드에 서로 연결 정보를 모두 저장해야 한다.

---

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, M;
bool visited[1001] = { false };
bool adjList[1001][1001];
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x = 0, y = 0;
        cin >> x >> y;
        adjList[x][y] = true;
        adjList[y][x] = true;
    }
}
 
void printInput() {
    cout << "N:" << N << "M:" << M << endl;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++)
            cout << adjList[i][j] << " ";
        cout << endl;
    }
}
 
bool bfs(int start) {
    if (visited[start]) //already visited node
        return false;
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= N; i++) {
            if (adjList[cur][i] && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    return true;
}
 
int countConnectedComponent() {
    int count = 0;
    for (int i = 1; i <= N; i++) {
        if (bfs(i))
            count++;
    }
    return count;
}
 
int main()
{
    input();
    //printInput();
    cout << countConnectedComponent() << endl;
}