[백준][Python] 11724번 연결 요소의 개수

11724번: 연결 요소의 개수

 

 

코드

def bfs(i):
	queue = []
	queue.append(i)
	while queue:
		num = queue.pop()
		for a in graph[num]:
			if visit[a] == 0:
				visit[a] = 1
				queue.append(a)
                
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
	u,v = map(int,input().split())
	graph[u].append(v)
	graph[v].append(u)
visit = [0]*(n+1)
cnt = 0
for i in range(1,n+1):
	if visit[i] == 0:
		cnt += 1
		bfs(i)
print(cnt)

 

설명

graph에 연결 정보를 저장해둔다.

1부터 n까지 차례대로 for문을 돌려서 아직 방문하지 않았다면 cnt 값을 1 증가시키고 그 점을 기준으로 bfs를 수행한다.