547.number-of-provinces.md

547. Number of Provinces

Union Find

We can use Union Find template to solve this problem.

fun findCircleNum(isConnected: Array<IntArray>): Int {
    val n = isConnected.size
    val uf = UnionFind(n)
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (i == j) continue
            if (isConnected[i][j] == 1) uf.union(i, j)
        }
    }
    return uf.componentCount
}

Traversal

Or we can use DFS/BFS to traverse the graph and count the number of connected components.

Please note that isConnected is a adjacency matrix of undirected graph.

fun findCircleNum(isConnected: Array<IntArray>): Int {
    val n = isConnected.size
    var count = 0
    val visited = BooleanArray(n) 
    for (i in 0 until n) {
        if (visited[i] == false) {
            dfs(isConnected, i, visited)
            count++
        }
    }
    return count
}

private fun dfs(isConnected: Array<IntArray>, i: Int, visited: BooleanArray) {
    val n = isConnected.size
    if (visited[i]) return
    visited[i] = true
    for (j in 0 until n) {
        if (isConnected[i][j] == 1) {
            dfs(isConnected, j, visited)
        }
    }
}