好友關系的連通分量數目

547. Friend Circles (Medium)

Input: [[1,1,0],[1,1,0],[0,0,1]]Output: 2Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. The 2nd student himself is in a friend circle. So return 2.

題目描述：

??好友關系可以看成是一個無向圖，例如第 0 個人與第 1 個人是好友，那么 M[0] [1]和 M[1] [0] 的值都為 1。

代碼：

public int findCircleNum(int [][]M){if(M==null||M.length==0)return 0;int n=M.length;boolean visited[]=new boolean[n]; //表示是否已經查看某人的朋友關系。int res=0;for(int i=0;i<n;i++){if(!visited[i]){ //該人沒有被查看過dfs(M,i,visited);res++;}}return res; } public void dfs(int [][]M,int i,boolean[]vistited){visited[i]=true; //表示已經訪問過該人的朋友關系for(int k=0;k<M.length;k++){if(M[i][k]==1&&!visited[k]){//判斷哪個人和i是朋友，然后再去檢查該人的朋友關系。dfs(M,k,visited);}} }

轉載于:https://www.cnblogs.com/yjxyy/p/11110298.html

總結

以上是生活随笔為你收集整理的搜索（DFS）---好友关系的连通分量数目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。