https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주www.acmicpc.net
bfs와 dfs중 하나를 선택해서 풀면 됨
먼져 visited를 만든다.
이후 모든 정점에 대하여 방문을 하지 않은 노드에서 탐색을 수행한다. 이때마다 1씩 정답을
증가시킨다.
주의할 점
1.양뱡향 그래프
- 컴퓨터는 숫자를 0부터 센다는걸 생각
이것만지키면 쉬움
##코드
from collections import dequeimport sysinput=sys.stdin.readlinedef bfs(i):
stack=deque([i]) while stack: tmp=stack.popleft()
for j in graph[tmp]: if not visited[j]:
stack.append(j) visited[j]=True
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)
visited=[False for _ in range(n+1)]answer=0for i in range(1,n+1):
if not visited[i]: bfs(i) answer+=1print(answer)