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

문제

---

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

11724번: 연결 요소의 개수

 

생각의 흐름

---

adjacent matrix를 만들어 dfs로 탐색한다.

 

깨달은 점

---

adjacent list를 만들어 dfs로 탐색하는 방법도 있다.(아래 코드를 첨부한다. 출처 : https://home-body.tistory.com/287)

 

코드

---

방법 1(adjacent matrix 이용)

import sys

N, M = 0, 0
arr = []
visit = []
cnt = 0

def dfs(x):

    if visit[x] == 1:
        return
    visit[x] = 1
    for i in range(N):
        if arr[x][i] == 1:
            dfs(i)


if __name__=='__main__':

    sys.setrecursionlimit(10**8)
    # N은 정점, M은 간선의 갯수
    N, M = map(int, sys.stdin.readline().split())
    arr = [[] for i in range(N)]
    visit = [0] * N

    for i in range(N):
        arr[i] = visit[:]

    for _ in range(M):
        u, v = map(int, sys.stdin.readline().split())
        arr[u-1][v-1] = 1
        arr[v-1][u-1] = 1

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

    print(cnt)

 

방법 2(adjacent list 이용)

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        if not visited[e]:
            dfs(e)
            
N, M = map(int, input().split())
adj = [[] for i in range(N+1)]
visited = [False] * (N + 1)
cnt = 0
 
for i in range(M):
    input_data = list(map(int, input().split()))
    adj[input_data[0]].append(input_data[1])
    adj[input_data[1]].append(input_data[0])
    
for i in range(1, len(visited)):
    if not(visited[i]):
        cnt += 1
        dfs(i)
        
print(cnt)