11724 연결 요소의 개수 python

휴대용치즈 2023. 1. 7. 19:57

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

문제 접근

dfs나 bfs로 풀릴것 같았지만, 따로 생각하지않고 느낌대로 적으면서 풀었다.

사실상 dfs로 풀었다.

visited로 연결된 선을 모두 체크하면서 진행했다.

1번부터 시작해서 연결된 선을 list에 저장해뒀다가 pop을 하면서 연결된 선의 수를 체크했다.

코드

from collections import deque
import sys
input = sys.stdin.readline

"""
왼쪽에서 pop하고 오른쪽에 push
k번째는 pop한 후에 push하지않음.

"""

N, M = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    u, v= map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
ans=0

visited=[False] * (N+1)
for i in range(1, N+1):
    if visited[i]:
        continue
    ans += 1

    list = [i]
    visited[i] = True
    while list:
        x = list.pop()
        for j in graph[x]:
            if not visited[j]:
                list.append(j)
                visited[j]=True

print(ans)

64940

704