leetcode 547. Friend Circles 并查集

本文主要是介绍leetcode 547. Friend Circles 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/friend-circles/

 

朋友关系是双向的，因此矩阵M是关于对角线对称的，只需要处理对角线以上的半边即可。

用一维数组 f [ ] 记录每个节点真实的根，使用并查集的方式，求出朋友圈的个数。

 

class Solution {
public:int findCircleNum(vector<vector<int>>& M) {int row = M.size();if(row == 0) return 0;int col = M[0].size();if(col == 0) return 0;int c = 0;int i, j;for(i=0;i<300;i++)//将每个节点的根初始化为它自己f[i]=i;for(i=0;i<row;i++){for(j=i+1;j<col;j++){if(M[i][j]==1){//如果两个点之间存在一条边，则将这两个点进行合并u(i, j);}}}for(i=0;i<row;i++)//如果一个点的根节点就是它自己，则这个点代表了一个朋友圈if(i==f[i])c+=1;return c;}int f[300];void u(int a, int b){ //并int x = find(a);int y = find(b);if(x!=y)f[x]=y;}int find(int x){ //查while(f[x]!=x)x = f[x];return x;}
};

 

 

 

这篇关于leetcode 547. Friend Circles 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---