백준 11724 - 연결 요소의 개수

문제 설명

 

 

=> graph의 연결 요소의 개수를 묻는 문제입니다. 

=> 기존의 DFS와 BFS를 이해하신 분이라면 쉽게 풀 수 있는 문제입니다. 

 

 

• 기존 방식대로기존 방식대로 입력을 받으며, 인접 행렬, 인접 리스트, 간선 리스트, check 행렬을 생성합니다. 

• 연결 요소의 개수를 확인해야하므로 DFS나 BFS를 통해 Path를 찾으며 해당 check 행렬을 최신화합니다. 

• 정점의 개수에 해당하는 check행렬이 모두 true가 될 때까지 진행합니다.

• 해당 프로세스를 진행하며 연결요소의 개수를 구합니다. 

 

 

 

 

*저는 DFS를 통해 연결요소의 개수를 셌습니다. 하지만 code에는 BFS함수까지 구현했으므로 BFS로 해도 무방합니다. 

*둘 중 어느 방법을 골라서 할지는 코드 작성자의 취향에 따라 갈립니다. 

 

 

<code>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>


using namespace std;

#define MAX 2001

bool check[1001];//갔다온지 확인하는 행렬
bool arr[MAX][MAX]; //인접행렬
vector<int> list[MAX]; //인접리스트
vector<pair<int,int>>edges; //간선리스트

void dfs(int x, int n)
{
    check[x]=true;
    for(int i=1; i<=n; i++)
    {
        if(arr[x][i] == true && check[i] ==false)//x, i가 연결되어있고 i를 가보지 않았던 경우
        {
            dfs(i, n);
        }
    }
}

void bfs(int x, int N)
{
    queue<int> q;
    check[x] = true;
    q.push(x);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i=1; i<=N; i++)
        {
            if(arr[x][i] == true && check[i] == false)
            {
                check[i] = true;
                q.push(i);
            }
        }
    }
    cout <<'\n';
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N, M; //정점 개수, 간선 개수
    cin >> N >> M;
 
    
    
    for(int i=0; i<M; i++)
    {
        int from,to;
        cin >> from >> to;
        edges.push_back({from, to});
        edges.push_back({to, from});
        arr[from][to] = arr[to][from] = true;
        list[from].push_back(to);
        list[to].push_back(from);
    }
    
    
    int cnt=0;
    
    for(int i = 1; i<=N; i++)
    {
        if(check[i] == true)
        {
            continue;
        }
        else{
            dfs(i, N);
            cnt++;
        }
    }
    
    cout << cnt <<'\n';
    return 0;
}

 

 

 

실행 화면 1

 

실행 화면 2