백준 11724번 - 연결요소의개수 (C++/ DP - 그래프(DFS,BFS))

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

접근법

인접행렬의 개수를 구하라는 것은 서로 연결되어 있지않은 그래프의 개수를 구하라는 것이다. 

 

간단한 BFS,DFS문제이다. 다만 끊겨있는 경우를 체크해야 하므로, BFS할때 visited를 사용해서 방문하지 않은 노드를 for문으로 지속적으로 방문해주면 된다.  

 

다만 인접행렬(정적배열)을 사용하지 말고 인접 리스트(vector)를 사용하는 것을 추천한다.

경우의 수가 노드는 N <= 1000 이기에, 인접행렬로 하면 연결되지 않은것들까지 체크해야하므로, 시간적으로 상당히 불리하다.

연결 리스트를 써서 구현하면 이러한 문제는 연결된 노드만 방문하면 되므로, 시간적으로 상당히 이득이 있다. 

이러한 점은 특히 그래프에서 중요한것 같다.

(내가 인접행렬써서 시간초과가 떴다 ㅎㅎ)

 

교훈 : 연결을 표시할때는 인접리스트(vector)를 사용하자. 

코드

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void BFS(int start, vector<bool>& visited, const vector<vector<int>>& adjList)
{
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty())
    {
        int here = q.front();
        q.pop();

        for (int there : adjList[here])
        {
            if (!visited[there])
            {
                q.push(there);
                visited[there] = true;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int V, A;
    cin >> V >> A;

    vector<vector<int>> adjList(V);
    vector<bool> visited(V, false);

    for (int i = 0; i < A; i++)
    {
        int from, to;
        cin >> from >> to;
        adjList[from - 1].push_back(to - 1);
        adjList[to - 1].push_back(from - 1);
    }

    int cnt = 0;

    for (int i = 0; i < V; i++)
    {
        if (!visited[i])
        {
            BFS(i, visited, adjList);
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}