백준 - 연결 요소의 개수 (11724)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])
var graph: [[Int]] = Array(repeating: [], count: N+1)
var visited = Array(repeating: false, count: N+1)
var answer = 0

// 인접 리스트 만들기
for _ in 0..<M {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph[input[1]].append(input[0])
    graph[input[0]].append(input[1])
}

for i in 1...N {
    if !visited[i] {
        answer += 1
        dfs(i)
    }
}

print(answer)

// 깊이 우선 탐색 함수
func dfs(_ v: Int) {
    visited[v] = true
    for u in graph[v] {
        if !visited[u] {
            dfs(u)
        }
    }
}

• DFS를 진행하는 횟수가 곧 연결 요소의 개수이다.
• 처음에는 DFS에서는 인접 리스트 방향이 상관 없을 줄 알고 크기가 작은 정점의 인접 리스트에 값이 더 큰 정점을 추가하는 식으로 코드를 짰는데, 100%에서 통과하지 못했다.
  • 그래서 양쪽 정점의 인접 리스트에 모두 정점을 추가해주었더니 통과가 됐다. 무방향 그래프라는 조건을 대충 넘기지 말자..