朋友圈

題目

班上有 N 名學(xué)生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我們可以認為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。

給定一個 N * N 的矩陣 M，表示班級中學(xué)生之間的朋友關(guān)系。如果M[i][j] = 1，表示已知第 i 個和 j 個學(xué)生互為朋友關(guān)系，否則為不知道。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)。

示例 1:

輸入: [[1,1,0], [1,1,0], [0,0,1]] 輸出: 2 說明：已知學(xué)生0和學(xué)生1互為朋友，他們在一個朋友圈。 第2個學(xué)生自己在一個朋友圈。所以返回2。

示例 2:

輸入: [[1,1,0], [1,1,1], [0,1,1]] 輸出: 1 說明：已知學(xué)生0和學(xué)生1互為朋友，學(xué)生1和學(xué)生2互為朋友，所以學(xué)生0和學(xué)生2也是朋友，所以他們?nèi)齻€在一個朋友圈，返回1。

注意：

N 在[1,200]的范圍內(nèi)。 對于所有學(xué)生，有M[i][i] = 1。 如果有M[i][j] = 1，則有M[j][i] = 1。

題解一：深度優(yōu)先搜索

給定的矩陣可以看成圖的鄰接矩陣。這樣我們的問題可以變成無向圖連通塊的個數(shù)。為了方便理解，考慮如下矩陣：

M= [1 1 0 0 0 0
    1 1 0 0 0 0
    0 0 1 1 1 0
    0 0 1 1 0 0
    0 0 1 0 1 0
    0 0 0 0 0 1]

，點的編號表示矩陣 M 的下標，iii 和 jjj 之間有一條邊當且僅當 M[i][j]M[i][j]M[i][j] 為 1。 為了找到連通塊的個數(shù)，一個簡單的方法就是使用深度優(yōu)先搜索，從每個節(jié)點開始，我們使用一個大小為 NNN 的 visitedvisitedvisited 數(shù)組（MMM 大小為 N×NN \times NN×N），這樣 visited[i]visited[i]visited[i] 表示第 i 個元素是否被深度優(yōu)先搜索訪問過。 我們首先選擇一個節(jié)點，訪問任一相鄰的節(jié)點。然后再訪問這一節(jié)點的任一相鄰節(jié)點。這樣不斷遍歷到?jīng)]有未訪問的相鄰節(jié)點時，回溯到之前的節(jié)點進行訪問。

public class Solution {
    public void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }
}

題解二：廣度優(yōu)先搜索

public class Solution {
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        Queue < Integer > queue = new LinkedList < > ();
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                queue.add(i);
                while (!queue.isEmpty()) {
                    int s = queue.remove();
                    visited[s] = 1;
                    for (int j = 0; j < M.length; j++) {
                        if (M[s][j] == 1 && visited[j] == 0)
                            queue.add(j);
                    }
                }
                count++;
            }
        }
        return count;
    }
}

題解三：并查集

public class Solution {
    int find(int parent[], int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }


    void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        if (xset != yset)
            parent[xset] = yset;
    }
    public int findCircleNum(int[][] M) {
        int[] parent = new int[M.length];
        Arrays.fill(parent, -1);
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {
                if (M[i][j] == 1 && i != j) {
                    union(parent, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == -1)
                count++;
        }
        return count;
    }
}

python3

class Solution:
    def findCircleNum(self, M) -> int:
        father = [i for i in range(len(M))]


        def find(a):
            if father[a] != a: father[a] = find(father[a])
            return father[a]


        def union(a, b):
            father[find(b)] = find(a)
            return find(b)


        for a in range(len(M)):
            for b in range(a):
                if M[a][b]: union(a, b)
        for i in range(len(M)): find(i)
        return len(set(father))