파이썬 백준 11724 연결 요소의 개수

정글러 2021. 11. 20. 22:15

import sys

input = sys.stdin.readline

Vn, En = map(int, input().split())

V = {}

for i in range(1, Vn + 1) :

V[i] = []

for i in range(En) :

v1, v2 = map(int, input().split())

V[v1].append(v2)

V[v2].append(v1)

gone = []

count = 0

def BFS(now) :

que = [now]

while que :

q = que[0]

gone.append(q)

del que[0]

for i in V[q] :

if not i in gone and not i in que :

que.append(i)

for i in range(1, Vn + 1) :

if not i in gone :

count = count + 1

BFS(i)

print(count)

입력받은 선의 정보대로 점의 연결관계를 기록한다.

함수의 실행점과 연결된 모든 점을 gone에 넣는 BFS를 정의한다.

모든 점에 for문을 돌면서 아직 gone에 들어가지 않았다면 BFS를 실행하면서 count +1

1주차의 안전 영역 문제와 같다.