Leetcode刷题java之547. 朋友圈（一天一道编程题之五十五天）

快来打我* 2023-07-24 13:23 29阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.92% 的用户

内存消耗 :40.7 MB, 在所有 Java 提交中击败了94.03%的用户

题目：

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N \* N 的矩阵 M，表示班级中学生之间的朋友关系。如果M\[i\]\[j\] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:  
\[\[1,1,0\],  
\[1,1,0\],  
\[0,0,1\]\]  
输出: 2  
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。  
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

输入:  
\[\[1,1,0\],  
\[1,1,1\],  
\[0,1,1\]\]  
输出: 1  
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

N 在\[1,200\]的范围内。  
对于所有学生，有M\[i\]\[i\] = 1。  
如果有M\[i\]\[j\] = 1，则有M\[j\]\[i\] = 1。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/friend-circles  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

利用并查集解决有几个连通块问题

参考：[https://leetcode-cn.com/problems/friend-circles/solution/union-find-suan-fa-xiang-jie-by-labuladong/][https_leetcode-cn.com_problems_friend-circles_solution_union-find-suan-fa-xiang-jie-by-labuladong]

代码：(并查集)

class Unionfind
    {
        //用一个数组来表示
        int[] parent;
        //表示树的大小，合并的时候将小的合并到大的上
        int[] size;
        //记录现在还有几块区域
        int count;
        //初始化，根节点的父节点等于本身，大小初始化为1
        public Unionfind(int count)
        {
            this.count=count;
            parent=new int[count];
            size=new int[count];
            for(int i=0;i<count;i++)
            {
                size[i]=1;
                parent[i]=i;
            }
        }
        public void Union(int p,int q)
        {
            int rootp=find(p);
            int rootq=find(q);
            if(rootp==rootq)
            {
                return;
            }
            //小的合并到大的上
            if(size[rootp]<size[rootq])
            {
                parent[rootp]=rootq;
                size[rootq]+=size[rootp];
                count--;
            }else
            {
                parent[rootq]=rootp;
                size[rootp]+=size[rootq];
                count--;
            }
        }
        //找到根节点，并进行路径压缩
        public int find(int x)
        {
            while(parent[x]!=x)
            {
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return x;
        }
        public boolean isConnected(int p,int q)
        {
            return find(p)==find(q);
        }
        public int getCount()
        {
            return count;
        }
    }
    class Solution {
        public int findCircleNum(int[][] M) {
            if(M.length==0)
            {
                return 0;
            }
            Unionfind UF=new Unionfind(M.length);
            for(int i=0;i<M.length;i++)
            {
                for(int j=i;j<M[0].length;j++)
                {
                    if(M[i][j]==1)
                    {
                        UF.Union(i,j);
                    }
                }
            }
            return UF.getCount();
        }
    }

代码：（深度）

class Solution {
        public int findCircleNum(int[][] M) {
            int[] visit=new int[M.length];
            int count=0;
            //表示对每个节点都进行深度遍历
            for(int i=0;i<M.length;i++)
            {
                if(visit[i]==0)
                {
                    visit[i]=1;
                    dfs(M,visit,i);
                    count++;
                }
            }
            return count;
        }
        public void dfs(int[][] M,int[] visit,int i)
        {
            for(int j=0;j<M.length;j++)
            {
                if(visit[j]==1||M[i][j]==0)
                {
                    continue;
                }
                visit[j]=1;
                dfs(M,visit,j);
            }
        }
    }

[https_leetcode-cn.com_problems_friend-circles_solution_union-find-suan-fa-xiang-jie-by-labuladong]: https://leetcode-cn.com/problems/friend-circles/solution/union-find-suan-fa-xiang-jie-by-labuladong/