문제
접근
파이썬에서 input을 사용해서 입력을 받으면, 입력이 많을 때 시간초과가 뜬다….
sys를 애용하자.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
import sys
n, m = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n+1)]
visit = [0] * (n+1)
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
adj[a].append(b)
adj[b].append(a)
def bfs(v):
queue = deque()
queue.append(v)
while queue:
node = queue.popleft()
for item in adj[node]:
if visit[item] == 0:
queue.append(item)
visit[item] = 1
ans = 0
for i in range(1,n+1):
if visit[i] == 0:
visit[i] = 1
bfs(i)
ans += 1
print(ans)