|
import sys
input = sys.stdin.readline
Vn = int(input())
En = int(input())
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)
for i in range(1, Vn + 1) :
V[i].sort()
gone = [1]
count = 0
def BFS(now) :
global count
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)
count = count + 1
BFS(1)
print(count)
|
그냥 이전 문제꺼 그대로 갖다쓰면 된다.
연결된 모든 점을 gone에 담는 BFS를 정의한 뒤 점 1에서 실행 후 카운트를 세면 끝
코드가 복사가 된다고
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 18352 특정 거리의 도시 찾기 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 2718 미로 탐색 (0) | 2021.11.20 |
| 파이썬 백준 11724 연결 요소의 개수 (0) | 2021.11.20 |
| 파이썬 백준 1260 DFS와 BFS (0) | 2021.11.19 |
| 파이썬 백준 1197 최소 스패닝 트리 (0) | 2021.11.19 |