Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- eecs 498
- 그래프 이론
- machine learning
- dynamic programming
- dfs
- DP
- YoLO
- 백준
- AlexNet
- 딥러닝
- hm3d
- Python
- NLP
- real-time object detection
- LSTM
- 머신러닝
- BFS
- two-stage detector
- MySQL
- Reinforcement Learning
- image processing
- Mask Processing
- CNN
- opencv
- deep learning
- r-cnn
- hm3dsem
- C++
- ubuntu
- 강화학습
Archives
- Today
- Total
JINWOOJUNG
[ 그래프 이론-11724 ] 연결 요소의 개수(Python) 본문
728x90
반응형
접근법
dfs를 활용하여 접근하였고, 방문하지 않은 노드에 대하여 dfs를 적용한다면, 연결된 노드들을 방문하고 만약 연결이 안된 다른 그룹이 있다면, 연결 요소의 개수를 증가시키고 다시 dfs를 적용시키면 된다.
정답
import sys
sys.setrecursionlimit(10**9)
M, N= map(int, sys.stdin.readline().split())
visited = [False]*(M+1)
graph = [[]for _ in range(M+1)]
for _ in range(N):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
def dfs(start):
visited[start] = True
for tmp in graph[start]:
if visited[tmp] == False:
dfs(tmp)
cnt = 0
for i in range(1,M+1):
if visited[i] == False:
cnt += 1
dfs(i)
print(cnt)
728x90
반응형
'백준' 카테고리의 다른 글
[ 그래프 이론-11725 ] 트리의 부모 찾기(Python) (1) | 2024.01.04 |
---|---|
[ 그래프 이론 - 4963 ] 섬의 개수(Python) (0) | 2024.01.03 |
[ 그래프 이론-2468 ] 안전 영역(Python) (1) | 2024.01.02 |
[ 그래프 이론-2668 ] 숫자고르기(Python) (0) | 2023.12.30 |
[ 자료구조-1253 ] 좋다(Python) (0) | 2023.12.29 |