알고리즘 문제풀이

백준 알고리즘 11724번:연결 요소의 개수 파이썬 코드 <문제풀이>

leezzangmin 2022. 3. 2. 11:37
반응형

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

 

import sys;input=sys.stdin.readline
sys.setrecursionlimit(10**8)
N,M=map(int,input().split())

graph=[ [] for _ in range(N+1) ]
visit=[ False for _ in range(N+1)]

for _ in range(M):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(i):
    visit[i]=True
    for x in graph[i]:
        if visit[x]==False:
            dfs(x)

ans=0
for i in range(1,N+1):
    if visit[i]==False:
        dfs(i)
        ans+=1

print(ans)

 

양방향 그래프인것을 간과하고 조금 헤맸다.

반응형