leetcode-kt/src/main/kotlin/problems/numberOfProvinces/Solution.kt at main · AxelUser/leetcode-kt · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package problems.numberOfProvinces

import readmeGeneration.ProblemDifficulty
import readmeGeneration.ProblemSolution

@ProblemSolution(
    547,
    "Number of Provinces",
    ProblemDifficulty.MEDIUM,
    "https://leetcode.com/problems/number-of-provinces/"
)
object Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        if (isConnected.size == 1) return 1
        var count = 0
        for (i in isConnected.indices) {
            if (isConnected[i][i] != -1) {
                count++
                isConnected[i][i] = -1
                dfs(isConnected, i)
            }
        }

        return count
    }

    private fun dfs(isConnected: Array<IntArray>, i: Int) {
        for (j in isConnected.indices) {
            if (i != j && isConnected[j][j] != -1 && isConnected[i][j] == 1) {
                isConnected[j][j] = -1
                dfs(isConnected, j)
            }
        }
    }
}