[python] 백준 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제 해결

그래프가 몇개로 분리되어있는지 개수를 세는 문제

visited 리스트를 통해 지나간 점을 체크하면서 1번부터 n번까지 dfs나 bfs를 돌리면서

몇번 돌려야 visited 리스트 원소가 모두 True가 되는지 count 한다고 생각하면 된다.

 

CODE(dfs)

import sys
sys.setrecursionlimit(5000)
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False]*(n+1)
def dfs(start):
    global visited
    visited[start] = True
    for next in graph[start]:
        if visited[next] == False:
            dfs(next)
    return
ans = 0
for i in range(1,n+1):
    if visited[i] == False:
        if not graph[i]:
            visited[i] = True
        else:
            dfs(i)
        ans +=1
print(ans)

CODE(bfs)

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

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
visited = [False]*(n+1)
def bfs(start):
    que = deque()
    que.append(start)
    visited[start] = True
    while que:
        now = que.popleft()
        for next in graph[now]:
            if not visited[next]:
                visited[next] = True
                que.append(next)
ans = 0
for i in range(n+1):
    if visited[i] == False:
        if not graph[i]:
            ans += 1
            visited[i] = True
        else:
            bfs(i)
            ans +=1
print(ans)