[백준/bfs] 11724번: 연결요소의 개수

-문제: https://www.acmicpc.net/problem/11724

쉬운데 괜히 어렵게 생각했던 문제.

기본 bfs를 구현한 다음에 bfs가 실행될 때마다 연결요소 개수가 증가한다고 생각하면 된다

만약 연결요소가 하나라면 bfs가 한번 실행된 후 모두 visited가 True일 것이므로 not visited가 더이상 발생하지 않아 bfs가 더는 실행되지 않고, cnt는 1이 된다 

 

-정답풀이: 

from collections import deque

def bfs(graph,v,visited):
    queue=deque()
    queue.append(v)
    visited[v]=True
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i]=True
                queue.append(i)
                
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
cnt=0
for i in range(1,n+1):
    if not visited[i]:
        bfs(graph,i,visited)
        cnt+=1
print(cnt)