547.省份数量

深度优先遍历

找到未访问过的城市，深度优先遍历其所有能联通的城市，并标记为已访问。

最后统计有几个联通量。

时间复杂度：O(N^2)
空间复杂度：O(N)

func findCircleNum(isConnected [][]int) int {
    ans := 0
    visited := make([]bool, len(isConnected))
    var dfs func(int)

    dfs = func(i int) {
        if visited[i] {
            return
        }
        visited[i] = true
        for j, connected := range isConnected[i] {
            if connected == 1 {
                dfs(j)
            }
        }
    }

    for i := 0; i < len(isConnected); i++ {
        if !visited[i] {
            dfs(i)
            ans++
        }
    }

    return ans
}