朋友圈

约定不等于承诺〃 2023-02-20 07:55 36阅读 0赞

## 一、前言 ##

问题来源LeetCode 547，难度：中等

问题链接：[https://leetcode-cn.com/problems/friend-circles/][https_leetcode-cn.com_problems_friend-circles]

## 二、题目 ##

班上有 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。

注意：

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

## 三、思路 ##

两种解决方法。

方法一：对于玩家0，若玩家0和玩家4是朋友，那么玩家4的所以玩家都和玩家0也是朋友，继续查找玩家4，玩家4和玩家8是朋友，也就是玩家0、4、8都是朋友是一个朋友圈。继续查找剩余的玩家（1、2、3、5、6、7、9）。

时间复杂度：O(n\*n)；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

方法二：并查集中的quick-find算法

时间复杂度：O(n\*n\*n)

## 四、总结 ##

这个问题用方法一解决就可以，思路也好理解。方法二提供了另外一种解题方法，并查集有三种方法，最高效益的是加权quick-union 算法，用于这道题时间复杂度也需要O(n\*n\*lgn)，慢与方法一。通过这道题可以学习了解一下并查集。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file    : 08_FindCircleNum.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/106956546
    * @author  : niebingyu
    * @title   : 朋友圈
    * @purpose : 班上有 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）128 困难
    * 链接：https://leetcode-cn.com/problems/friend-circles
    */
    //==========================================================================
    #pragma once
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_FINDCIRCLENUM namespace NAME_FINDCIRCLENUM {
    #define NAMESPACE_FINDCIRCLENUMEND }
    NAMESPACE_FINDCIRCLENUM
    
    // 方法一
    class Solution_1
    {
    public:
        int findCircleNum(vector<vector<int>>& M)
        {
            int len = (int)M.size();
            vector<int>group(len);
            for (int i = 0; i < len; i++)
            {
                group[i] = i;
            }
    
            int ret = len;
            vector<int>t(len,0);
            list<int> l;
            for (int i = 0; i < len; ++i)
            {
                if (t[i] == 0)
                {
                    l.push_back(i);
                    while (!l.empty())
                    {
                        int nu = l.front();
                        t[nu] = 1;
                        l.pop_front();
                        for (int j = 0; j < len; j++)
                        {
                            if(M[nu][j] == 1 && i != group[j])
                            {
                                group[j] = i;
                                ret--;
                                l.push_back(j);
                            }
                        }
    
                    }
                }
            }
            
            return ret;
        }
    };
    
    // 方法二：并查集
    class Solution_2
    {
    public:
        int findCircleNum(vector<vector<int>>& M)
        {
            int len = (int)M.size();
            vector<int> parent(len, -1);
            for (int i = 0; i < len; ++i)
            {
                for (int j = i + 1; j < len; ++j)
                {
                    if (M[i][j] == 1 && i != j)
                        Union(parent, i, j);
                }
            }
    
            int count = 0;
            for (int i = 0; i < len; ++i)
                if (parent[i] == -1)
                    count++;
    
            return count;
        }
    
    private:
        int find(vector<int>& Vec, int n)
        {
            if (Vec[n] == -1)
                return n;
            return find(Vec, Vec[n]);
        }
    
        void Union(vector<int>& Vec, int m, int n)
        {
            int parent_m = find(Vec, m);
            int parent_n = find(Vec, n);
            if (parent_m != parent_n)
                Vec[parent_n] = parent_m;
        }
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, vector<vector<int>>& M, int expect)
    {
        Solution_1 S1;
    	Solution_2 S2;
    	int result1 = S1.findCircleNum(M);
        int result2 = S2.findCircleNum(M);
    
    	// 粗略校验
    	if (result1 == expect && result2 == expect)
    		cout << testName << ", solution12 passed." << endl;
    	else
    		cout << testName << ", solution failed. result1:" << result1 << ", result2:" << result2 << " ,expect:" << expect << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<int>> nums =
        {
            {1,1,0},
            {1,1,0 },
            {0,0,1 }
        };
    
        int expect = 2;
    
        test("Test1()", nums, expect);
    }
    
    void Test2()
    {
        vector<vector<int>> nums =
        {
            {1,1,1},
            {1,1,0 },
            {1,0,1 }
        };
    
        int expect = 1;
    
        test("Test2()", nums, expect);
    }
    
    void Test3()
    {
        vector<vector<int>> nums =
        {
            {1,0,0,1},
            {0,1,1,0},
            {0,1,1,1},
            {1,0,1,1}
        };
    
        int expect = 1;
    
        test("Test3()", nums, expect);
    }
    
    void Test4()
    {
        vector<vector<int>> nums =
        {
            {1,1,1,0},
            {1,1,0,0},
            {1,0,1,1},
            {0,0,1,1}
        };
    
        int expect = 1;
    
        test("Test4()", nums, expect);
    }
    
    void Test5()
    {
        vector<vector<int>> nums =
        {
            { 1,1,0,0,0,0,0,1,0,0,0,0,0,0,0 },
            { 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0 },
            { 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0 },
            { 0,0,0,1,0,1,1,0,0,0,0,0,0,0,0 },
            { 0,0,0,0,1,0,0,0,0,1,1,0,0,0,0 },
            { 0,0,0,1,0,1,0,0,0,0,1,0,0,0,0 },
            { 0,0,0,1,0,0,1,0,1,0,0,0,0,1,0 },
            { 1,0,0,0,0,0,0,1,1,0,0,0,0,0,0 },
            { 0,0,0,0,0,0,1,1,1,0,0,0,0,1,0 },
            { 0,0,0,0,1,0,0,0,0,1,0,1,0,0,1 },
            { 0,0,0,0,1,1,0,0,0,0,1,1,0,0,0 },
            { 0,0,0,0,0,0,0,0,0,1,1,1,0,0,0 },
            { 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0 },
            { 0,0,0,0,0,0,1,0,1,0,0,0,0,1,0 },
            { 0,0,0,0,0,0,0,0,0,1,0,0,0,0,1 },
    
        };
    
        int expect = 3;
    
        test("Test5()", nums, expect);
    }
    
    NAMESPACE_FINDCIRCLENUMEND
    // 测试 用例 END
    //
    
    void FindCircleNum_Test()
    {
        NAME_FINDCIRCLENUM::Test1();
        NAME_FINDCIRCLENUM::Test2();
        NAME_FINDCIRCLENUM::Test3();
        NAME_FINDCIRCLENUM::Test4();
        NAME_FINDCIRCLENUM::Test5();
        NAME_FINDCIRCLENUM::Test5();
    }

**执行结果：**

![20200625114304494.png][]

[https_leetcode-cn.com_problems_friend-circles]: https://leetcode-cn.com/problems/friend-circles/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200625114143487.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200625114304494.png]: https://img-blog.csdnimg.cn/20200625114304494.png