题目

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

题解

简单并查集题目而且N范围在[1,200] 直接dfs也可以(dfs代码行数少的贼舒服)

代码

1.并查集


fun findCircleNum1(M: Array<IntArray>): Int {
    var parent: IntArray = IntArray(M[0].size)
    var count = 0
    init(parent)
    for (i in M.indices) {
        for (j in M[i].indices) {
            if (j == i)
                continue
            if (M[i][j] == 1)
                merge(i, j, parent)
        }
    }
    for (i in parent.indices)
        if (i == parent[i])
            count++
    return count
}

fun init(parent: IntArray) {
    for (i in parent.indices)
        parent[i] = i
}

fun find(x: Int, parent: IntArray): Int {
    var k: Int
    var j: Int
    var r = 0
    r = x
    while (r != parent[r])
        r = parent[r]
    k = x
    while (k != r) {
        j = parent[k]
        parent[k] = r
        k = j
    }
    return r
}

fun merge(x: Int, y: Int, parent: IntArray) {
    var x1 = find(x, parent)
    var y1 = find(y, parent)
    if (x1 == y1)
        return
    if (x1 < y1) {
        parent[y1] = x1
    } else {
        parent[x1] = y1
    }

}

2.dfs


lateinit var vist: IntArray
lateinit var map: Array<IntArray>

fun findCircleNum(M: Array<IntArray>): Int {
    var count = 0
    vist = IntArray(M.size)
    map = M

    for (i in M.indices) {
        if (vist[i] == 0) {
            dfs(i)
            count++
        }
    }
    return count
}

fun dfs(x: Int) {
    vist[x] = 1
    for (i in map.indices)
        if (vist[i] == 0 && map[x][i] == 1)
            dfs(i)
}