這篇文章將為大家詳細(xì)講解有關(guān)leetcode中如何解決朋友圈的問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)秉承實現(xiàn)全網(wǎng)價值營銷的理念，以專業(yè)定制企業(yè)官網(wǎng)，成都網(wǎng)站設(shè)計、網(wǎng)站制作、外貿(mào)營銷網(wǎng)站建設(shè)，成都小程序開發(fā)，網(wǎng)頁設(shè)計制作，成都做手機網(wǎng)站，成都營銷網(wǎng)站建設(shè)幫助傳統(tǒng)企業(yè)實現(xiàn)“互聯(lián)網(wǎng)+”轉(zhuǎn)型升級專業(yè)定制企業(yè)官網(wǎng),公司注重人才、技術(shù)和管理，匯聚了一批優(yōu)秀的互聯(lián)網(wǎng)技術(shù)人才,對客戶都以感恩的心態(tài)奉獻(xiàn)自己的專業(yè)和所長。

班上有 N 名學(xué)生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我們可以認(rèn)為 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。

解題思路

1，給定的矩陣可以看成圖的鄰接矩陣。這樣我們的問題可以變成無向圖連通塊的個數(shù)。

2，計算連通塊的算法有，深度優(yōu)先，廣度優(yōu)先和并查集

3，思路都一樣：將連通的部分染上色，直至沒有連通的點，就得到了一個聯(lián)通塊。

4，遍歷整個矩陣就得到了所有連通塊。

代碼實現(xiàn)：

func findCircleNum(M [][]int) int {    count:=0    visited:=make([]int,len(M))    for i:=0;i        if visited[i]==0{            count++            dfs(M,visited,i)        }    }    return count}
func dfs(M[][]int,visited[]int,i int){    for j:=0;j        if M[i][j]==1&&visited[j]==0{            visited[j]=1            dfs(M,visited,j)        }    }}

關(guān)于“l(fā)eetcode中如何解決朋友圈的問題”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。