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

문제

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

 

입력

n: Int = 정점의 개수
m: Int = 간선의 개수

u: 간선의 정점1
v: 간선의 점점2

1 <= n <= 1000
0 <= m <= (n*(n-1))/2
u != v

결과

ans: Int = 그래프에 존재하는 연결 컴포넌트 개수

해석

제공된 간선 정보를 이용해서 인접 행렬을 채운다.

이후 dfs를 통해 방문여부를 갱신하여 중복하여 방문하는 문제를 해결한다.

코드

import Foundation

let nm = readLine()!.split{$0 == " "}.map{Int($0)!}

let (n, m) = (nm[0], nm[1])

var adj: [[Int]] = [[Int]](repeating: [], count: n+1)

for _ in 0..<m {
    let ab = readLine()!.split{$0 == " "}.map{Int($0)!}
    let (a,b) = (ab[0], ab[1])
    adj[a].append(b)
    adj[b].append(a)
}

var visited: [Bool] = [Bool](repeating: false, count: n+1)


func dfs(_ now: Int) {
     visited[now] = true
    
    for next in adj[now]{
        if visited[next] {
            continue
        }
        dfs(next)
    }
    
}

var ans: Int = 0

for root in 1...n {
    if !visited[root] {
        dfs(root)
        ans += 1
    }
}

print(ans)