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 directfriend 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 directfriends 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.
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,
Note:
这个题的解法是有不唯一的。还有,这个题与那个统计油田的个数的BFS和DFS的模板题是不一样的。 参考链接:http://www.cnblogs.com/grandyang/p/6686983.html 第一种解法: BFS 对于某个人,我们可以先遍历其好友(如果他有好友),然后再遍历好友的好友,一直继续下去,直到不能继续找到好友为止,可以找出一个朋友圈内的所有好友。接下来再对于还没有遍历的人,继续同样的方法,直到遍历完我所有人为止,此时,我们可以统计朋友圈的个数。注意,每当遍历到人时,要标记已经遍历过的。
C 代码: class Solution { public: int findCircleNum(vector<vector<int>>& M) { queue<int> q; int m = M.size(); int res = 0; vector<bool> vis(m,false); for(int i = 0; i < m; i ){ if(vis[i] == true) continue; //如果已经遍历过,就略过,因为这个人所在的朋友圈已经遍历了。 q.push(i); while(!q.empty()){ int t = q.front();q.pop(); vis[t] = true; for(int j = 0; j < m; j ){ if(M[t][j] && !vis[j]){ q.push(j); } } } res ; } return res; } };
第二种解法: DFS,思路和上面的BFS类似。 class Solution { public: void dfs(vector<vector<int>> &M,int i,vector<bool> &vis){ int m = M.size(); vis[i] = true; //把遍历到的人标记为已经遍历的。 for(int j = 0; j < m; j ){ if(M[i][j] == 1 && !vis[j]){ dfs(M,j,vis); } } } int findCircleNum(vector<vector<int>>& M) { int m = M.size(); int res = 0; vector<bool> vis(m,false); for(int i = 0; i < m; i ){ if(vis[i] == true) continue; dfs(M,i,vis); res ; //一路“莽”到底后,递增res,指的是朋友圈的个数的增加。 } return res; } }; 来源:http://www./content-4-194101.html |
|