[백준] 11724_연결 요소의 개수 (Python)

11724_연결 요소의 개수 (Python)

0. 출처

• 유형 : 탐색 (silver 2)
• 링크 : 11724번: 연결 요소의 개수

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
6 5
graph = [[], [2,5]. [1,5], [4], [3,6], [2,1], [4]]
visited = [[], [True], [True], [False], [Faase], [True], [False]]

>> 위의 형태로 만들어 줄 것임

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
정점의 개수 n / 간선의 개수 m
6 5
1 2
2 5
5 1
3 4
4 6

- 예제 출력 1 -
2

- 예제 입력 2 -
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

- 예제 출력 2 -
1

(3) 코드

import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


n, m = map(int, input().split())

graph = [[] * m for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]

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


# fixme - flag로 노드 덩어리에 대해 탐색을 진행했는지 파악한다.
def iterative_bfs(s):
    q = deque([])
    q.append(s)
    flag = 0

    if visited[s] == False:
        visited[s] = True
        flag = 1

    while q:
        v = q.popleft()
        for w in graph[v]:
            if visited[w] == False:
                q.append(w)
                visited[w] = True

    return flag


# fixme - 노드 덩어리의 갯수를 찾아주기 위함
cnt = 0

for s in range(1, n + 1):
    flag = iterative_bfs(s)
    if flag == 1:
        cnt += 1

print(cnt)

(4) 정리

flag 로 방문하지 않는 노드 덩어리의 탐색 여부를 확인합니다.
flag 가 1인 경우 탐색을 했다는 의미이고 flag 가 0인 경우는 노드 덩어리를 찾지못했다는 의미입니다.

(5) 참고