.net 网站模板 下载,昌大建设集团大老板,网站怎么使用,关于门户网站建设的整改报告问题来源
此题来源于LeetCode547. Friend Circles#xff0c;主要运用了并查集#xff08;union find#xff09;、广度优先遍历#xff08;bfs#xff09;和深度优先遍历#xff08;bfs#xff09;三种方法解决。
问题简述
给定一个NN的矩阵M表示了N个人之见的朋友关…问题来源
此题来源于LeetCode547. Friend Circles主要运用了并查集union find、广度优先遍历bfs和深度优先遍历bfs三种方法解决。
问题简述
给定一个N×NN \times N的矩阵MM表示了NN个人之见的朋友关系。如果M[i][j]1M[i][j]=1那么ii和jj是直接朋友关系如果M[i][j]1M[i][j]=1M[j][k]1M[j][k]=1M[i][k]0M[i][k]=0那么ii和kk是间接朋友关系。我们假定有直接和间接朋友关系的人为一个朋友圈试问MM中有几个朋友圈。
比如：输入:
[[1,1,0],[1,1,0],[0,0,1]]
输出: 2
解释:第0和第1个人是直接朋友，他们构成1个朋友圈；第2个人自己构成一个朋友圈，所以返回2。又比如：输入:
[[1,1,0],[1,1,1],[0,1,1]]
输出: 1
解释：第0和第1个人是直接朋友，第1和第2个人是直接朋友，所以第0和第2个人是间接朋友，这3个人构成了1个朋友圈，所以返回1。 值得注意的是：
总是有M[i][j]=M[j][i]M[i][j]=M[j][i]
总是有M[i][i]1M[i][i]=1解决方案
利用union find解决
此处的并查集用到了路径压缩的优化。
class Solution {
private:vectorint vec;int sz;private:void Initialize(int count){vec vectorint(count);sz count;for (int i 0; i count; i)vec[i] i;}int findRoot(int p){assert(p 0 p sz);while (vec[p] ! p){//路径压缩vec[p] vec[vec[p]];p vec[p];}return vec[p];}void unionNode(int p, int q){assert(p 0 p sz q 0 q sz);int pRoot findRoot(p);int qRoot findRoot(q);if (pRoot ! qRoot)vec[pRoot] qRoot;}public:int findCircleNum(vectorvectorint M) {int m M.size();if (0 m)return 0;Initialize(m);for (int i 0; i m; i){for (int j i 1 ; j m; j){if (M[i][j] 1)unionNode(i, j);}}int res 0;for (int i 0; i m; i)if (vec[i] i)res;return res;}
};
利用bfs解决
由于问题的特殊性每次都只要把对角线上的元素放到队列当中即可。
class Solution {
private:int sz;private:void bfs(vectorvectorint M, int x){queueint q;q.push(x);while(!q.empty()){int newX q.front();q.pop();M[newX][newX] 0;for (int i 0; i sz; i){if (1 M[newX][i]){M[newX][i] 0;M[i][newX] 0;if (1 M[i][i])q.push(i);}}}return;}public:int findCircleNum(vectorvectorint M) {int m M.size();if (0 m)return 0;sz m;int res 0;for (int i 0; i m; i){if (1 M[i][i]){bfs(M,i);res;}} return res;}
};
利用dfs解决
dfs与bfs的思路大同小异但元素过多可能会造成栈溢出。
class Solution {
private:int sz;private:void dfs(vectorvectorint M, int x, int y){if (0 M[x][y])return;M[x][y] 0;for (int i 0; i sz; i){if (1 M[x][i]){M[x][i] 0;M[i][x] 0;dfs(M, i, i);}}return;}public:int findCircleNum(vectorvectorint M) {int m M.size();if (0 m)return 0;sz m;int res 0;for (int i 0; i m; i){if (1 M[i][i]){dfs(M,i,i);res;}} return res;}
};
结束语
以上三种方法最快的是并查集union findbfs和dfs的速度差不多三者也许都还有优化的余地~
