11724번

11724번 - 연결 요소의 개수

문제를 보자마자 연결요소란 개념을 몰라서 찾아서 풀어야 했다.

연결 요소란 위의 그림 같이 그래프가 다 이어지지 않고 나뉜 경우를 말한다고 한다.

따라서 위에서 연결 요소의 갯수는 2가 된다.

이처럼 연결요소는 BFS 나 DFS 를 각 노드 마다 돌려서 확인하면 된다.

< BFS 풀이 >

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int N, M;
vector<int> node[1001];
bool check[1001];
queue<int> q;
int ans;
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++)
    {
        
        if (!check[i])
        {
            ans += 1;
            q.push(i);
            check[i] = true;
 
            while (!q.empty())
            {
                int now = q.front();
                q.pop();
 
                for (int i = 0; i < node[now].size(); i++)
                {
                    int next = node[now][i];
                    if (!check[next])
                    {
                        check[next] = true;
                        q.push(next);
                    }
                }
            }
        }
 
 
    }
 
    cout << ans << endl;
 
    return 0;
}

< DFS 풀이 >

#include<iostream>
#include<vector>
using namespace std;
 
int N, M;
vector<int> node[1001];
bool check[1001];
int ans;
void dfs(int start)
{
    check[start] = true;
 
    for (int j = 0; j < node[start].size(); j++)
    {
        if (!check[node[start][j]])
        {
            dfs(node[start][j]);
        }
    }
 
    return;
}
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (!check[i])
        {
            ans += 1;
            dfs(i);
        }
    }
 
    cout << ans << endl;
 
    return 0;
}