[BFS] 백준 11724번 연결 요소의 개수(C++)

https://www.acmicpc.net/problem/11724

짜잔

 

난 솔직히 이거 처음 봤을때 뭔소린가 했다.

연결 요소란 개념을 먼저 알고 있어야 한다

 

연결요소는 간단하다

 

앞선 BFS , DFS에서 우리는 그래프 개념을 사용해서 문제를 풀었고

 

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

안풀어봤으면 꼭 풀어보고 와라

 

 

각 노드들은 서로 연결되어 있었다.

 

이때, 각각 서로 독립인 노드들의 갯수를 얘기하는 것이다

 

예를들어 설명하자면

 

사이트에 나온 예시를 시각화 하여 표현한 것이다.

 

1 2 5와 3 4 6 은 서로 독립되어 보이지 않는가?

 

그렇다 이것이 연결 요소인 것이다

 

독립된 노드들의 집합이 2개가 있으니 이것의 값은 2가 나온 것이고

 

이 예제에 대해선

 

 

이런 형태로 되어 있으니 독립된 노드들이 1개로 뜨는 것이다

 

 

그럼 먼저 생각해야 하는것은

 

1. 독립된 노드들을 확인하는 방법

2. 갯수 세기

 

먼저 1번에 대해선

우리는 저번 시간에 BFS와 DFS에 대해서 풀었었는데

 

둘 중 어느것을 쓰더라도 "연결된 모든 노드들을 탐색"하는 것엔 변함 없었다.

 

그렇다면?

1.각 번호에 대해 BFS or DFS를 사용하여 노드들의 집합을 확인한다

2.해당 노드들의 집합을 모두 확인햇다면 아직 방문하지 않은 다른 노드들에 접근하여 앞선 1번을 진행한다

 

#include <iostream>

#include <vector>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

int n, m;

vector<int> v[10002];

bool visited[1002];

void bfs();

int count_ = 0;

int main()

{

    cin >> n >> m;

    for (int i = 0; i < m; i++)

    {

        int x, y;

        cin >> x >> y;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    bfs();

    cout << count_ << "\n";

}

void bfs()

{

    for (int k = 1; k <= n; k++)

    {

        queue<int> q;

        q.push(k);

        vector<int> a;

        if (!visited[k])

        {

            visited[k] = true;

            while (!q.empty())

            {

                int x = q.front();

                a.push_back(x);

                q.pop();

                for (int i = 0; i < v[x].size(); i++)

                {

                    if (!visited[v[x][i]])

                    {

                        visited[v[x][i]] = true;

                        q.push(v[x][i]);

                    }

                }

            }

            count_++;

        }

    }

}

 

bfs나 dfs나 둘 중 하나를 사용해서 문제를 풀면 되는 것이다.

둘다 풀어보길 바람~