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

예제 1번에서 이런 모습이 된다. 사실 bfs를 써도 되고 , dfs를 써도 상관없다.

C++풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v[1001];
queue<int> q;

bool visited[1001];
int cnt = 0;
void bfs(){
    
    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        for(int i = 0; i<v[node].size(); i++)
        {
            if(visited[v[node][i]] == false)
            {
                visited[v[node][i]] = true;
                q.push(v[node][i]);
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    for(int i = 0 ; i< M; i++) // 간선정보들을 양방향으로 받고
    {
        int s,e;
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
    
    for(int i = 1 ; i<= N; i++) //모든 노드들을 방문하는데
    {
        if(visited[i] == false) // 방문하지 않았던 노드들만 방문함.
        {
            cnt++;
            visited[i] = true;
            q.push(i);
            bfs(); // bfs탐색해서 연결된 노드들을 모두 방문하고 빠져나옴.
        }
        //연결되지 않았던 노드들이 탐색되고 다시 bfs탐색하면서 count+1씩 될거임.
    }
    cout << cnt;
}

Python 풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    global dq, visited,node
    while dq:
        n = dq.popleft()
        for i in node[n]:
            if visited[i] == False:
                visited[i] = True
                dq.append(i)

N,M = map(int, input().strip().split())
dq = deque()
node = [[] for _ in range(N+1)] 
visited = [False] * (N+1)

for _ in range(M):
    s, e = map(int, input().strip().split())
    node[s].append(e)
    node[e].append(s)

cnt =0
for i in range(1,N+1):
    if not visited[i]:
        cnt +=1 
        visited[i] = True
        dq.append(i)
        bfs()

print(cnt)