[Python/파이썬 11724 백준] 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

풀이

처음에 연결요소를 몰라서

구글링한 결과

그냥 이어진 덩어리를 말하는거 였네요.

간선으로 이어졌으면 한 덩어리입니다.

 

그래서

이 문제는 dfs나 bfs로

0~n 점까지 bfs를 써서

이어진 모든 점들을 구해주고 방문한 점은 check를 True로 하여

몇번 bfs 돌렸는지 갯수를 셌습니다!

 

# 연결 요소의 개수

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

n,m=map(int,input().split())

lst=[[] for _ in range(n)]
check=[False for _ in range(n)]
total=0
queue=deque()

for i in range(m):
    x,y=map(int,input().split())
    lst[x-1].append(y-1)
    lst[y-1].append(x-1) 

def bfs(x):
    global total
    check[x]=True
    
    for nx in lst[x]:
        if check[nx]==False:
            queue.append(nx)
    # 덱 사용해서 False일 시, 삽입
    while queue:
        x=queue.popleft()
        for nx in lst[nx]:
            if check[nx]==False:
                queue.append(nx)
                check[nx]=True
    # 이어진곳 전부 다 순환하면 +1           
    total+=1

# 0~n까지 전부 다 체크
for i in range(n):
    if not check[i]:
        bfs(i)
    
print(total)