題目：

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.

Example 1:

Input: [[1,1,0],[1,1,0],[0,0,1]] Output: 2 Explanation: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.

Example 2:

Input: [[1,1,0],[1,1,1],[0,1,1]] Output: 1 Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

N is in range [1,200].

M[i][i] = 1 for all students.

If M[i][j] = 1, then M[j][i] = 1.

題意及分析：求朋友圈個數，若M[i][j]==1，則i,j為朋友，朋友有傳遞性，直接朋友或者間接朋友組成一個朋友圈。按照圖論的方式來講給出一個圖的鄰接矩陣，求不相鄰的子圖個數。我第一次用了寬度遍歷，對于其中一個點M[i][j]，若該點未被遍歷過，則把該點標記為已遍歷，然后遍歷第i,j行和i,j列（即寬度遍歷），找到為1的且未被遍歷過的點，重復操作。但是此方法時間復雜度較高，排名基本上在最后面了。。。 另一種是聲明一個visited，用于記錄遍歷過的結點。每次dfs找到一個原矩陣為1的位置（除了對角線），就把這個位置的列數變成行數再dfs，如果是在同一個圈里，最終會繞回已經遍歷過的行，visited為true，return 0；如果不是同一個圈，則增加1。（mat[i][j]==1這個判斷相當于i的鄰接點，深度優先遍歷）
代碼：

public class Solution {public int findCircleNum(int[][] M) {int res = 0;int row= M.length;if(row==0) return 0;for(int i=0;i<row;i++){ //只遍歷矩陣下半部分for(int j=0;j<=i;j++){if(M[i][j]==1){ //未被遍歷過的值為1的點res++;boolean[] rowVisited = new boolean[row]; //記錄已經遍歷過的行boolean[] colVisited = new boolean[row]; //記錄已經遍歷過的列Integer[] index = {i,j};Queue<Integer[]> queue = new LinkedList<>();queue.add(index); //查找該個點組成的朋友圈,能和該點組成朋友圈的點滿足在i,j行或者i,j列while(!queue.isEmpty()){Integer[] val = queue.poll();int x =val[0],y=val[1];if(M[x][y]==1){ //防止重復M[x][y] = 2; //將遍歷過的點置為2if(!rowVisited[x]){for(int m=0;m<=x;m++){ //x行Integer[] addIndex = {x,m};if(M[x][m]==1 && !queue.contains(addIndex)) queue.add(addIndex);}rowVisited[x]=true;}if(!rowVisited[y]){for(int n=0;n<=y;n++){ //第y行Integer[] addIndex = {y,n};if(M[y][n]==1) queue.add(addIndex);}rowVisited[y]=true;}if(!colVisited[x]){for(int m=x;m<row;m++){ //第x列Integer[] addIndex = {m,x};if(M[m][x]==1&& !queue.contains(addIndex)) queue.add(addIndex);}colVisited[x]=true;}if(!colVisited[y]){for(int m=y;m<row;m++){ //第y列Integer[] addIndex = {m,y};if(M[m][y]==1&& !queue.contains(addIndex)) queue.add(addIndex);}colVisited[y]=true;}}}}}}return res;} }

?代碼：

public class Solution {public int findCircleNum(int[][] M) {if (M == null && M.length == 0)return 0;int n = M.length;boolean[] visited = new boolean[n];int count = 0;//如果dfs大于0，說明有未遍歷的結點//只需要遍歷所有結點for (int i = 0; i < n; i++)if (dfs(M, i, visited) > 0)count++;return count;}private int dfs(int[][] mat, int i, boolean[] visited) {if (visited[i])return 0;visited[i] = true;int count = 1;for (int j = 0; j < visited.length; j++)if (i != j && mat[i][j] == 1)count += dfs(mat, j, visited);return count;} }

?

轉載于:https://www.cnblogs.com/271934Liao/p/7245550.html

總結

以上是生活随笔為你收集整理的[LeetCode] 547. Friend Circles Java的全部內容，希望文章能夠幫你解決所遇到的問題。

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