由一道面试题到并查集

我不是女神ヾ 2022-07-14 08:12 122阅读 0赞

## 面试题引入 ##

问题描述：

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），

则认为他们属于同一个朋友圈，

请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5， m = 3， r = \{ \{1 , 2\} , \{2 , 3\} ,\{4 , 5\}\}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，

则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

## 问题分析 ##

这道题本质上是其实是求解一个图中有多少无向连通分量的问题，如下图：  
![这里写图片描述][20161203111044242]

上图1，2，3，4，5可以看作是一个图中的节点， r = \{ \{1 , 2\} , \{2 , 3\} ,\{4 , 5\}\}是这个图中顶点与顶点之间的连接关系。我们要求构成朋友圈的个数，只要求图中连通图的个数即可，如本题中的链接关系，我们可知道图中最小连通图的个数为2，所以构成朋友圈的个数为2。  
虽然这种解法可以得到问题的最终结果但是这种解法需要遍历整个图，如果是邻接表来表示图，那么遍历整个图的时间复杂度为O(N\*N),还有建立图等问题也有时间复杂度的消耗，所以总的来说这不是面试官喜欢的解法。

## 时间复杂度为O(N)的解法 ##

本题中r = \{ \{1 , 2\} , \{2 , 3\} ,\{4 , 5\}\}可以看成是一个大集合，里面的各个朋友关系可以看成是这个大集合中的子集，当两个子集中有相同的元素，可以把这两个子集合并成一个子集，最后我们只需要统计出大集合中子集的个数就能知道一共有多少个朋友圈了。  
在这里向大家介绍一种数据结构可以很好的解决这个问题：  
这种结构叫做并查集，它实际上是一个数组数组上的元素存储的是一个集合中的顶点元素，在这个集合中的元素都要与这个顶点相连。与顶点相连的下标对应的元素存储的是顶点下标，它能把题中构成朋友圈关系的元素元素放在同一个集合中具体操作如下图：  
![这里写图片描述][20161203113813918]

开始时我们把数组中所有的元素都初始化成-1当我们把 r = \{ \{1 , 2\} , \{2 , 3\} ,\{4 , 5\}\}中的子集两两在并查集中合并时，只要我们找到数组中小于0的元素的个数我们就能找到集合中有多少组朋友圈了。

## 代码 ##

#include <iostream>
    using namespace std;
    #include <cassert>
    #include <vector>
    
    template<class T>
    class UnionSet
    {
    public:
        UnionSet(const size_t& size)
            :_size(size)
        {
            _a.resize(size);
            for (int i = 0; i < _size; i++)
            {
                _a[i] = -1;
            }
        }
    
        int FindParent(int x)
        {
            while (_a[x] >= 0)
            {
                x = _a[x];
            }
            return x;
        }
    
        int ReturnCount()
        {
            int count = 0;
            for (int i = 0; i < _size; i++)
            {
                if (_a[i] < 0)
                {
                    count++;
                }
            }
            return count-1;
        }
    
        int ReturnRoot(size_t x)
        {
            while (_a[x]>=0)
            {
                x = _a[x];
            }
            return x;
        }
    
        void Merge(size_t x1, size_t x2)
        {
            assert(x1 < _size&&x2 < _size);
            int parent1 = FindParent(x1);
            int parent2 = FindParent(x2);
    
            if (parent1 != parent2)
            {
                _a[parent1] += _a[parent2];
                _a[parent2] = parent1;
            }
        }
    protected:
        vector<int> _a;
        size_t _size;
    };
    
    int Friends(int m, int n, int a[][2])
    {
        UnionSet<int> s(n+1);
        for (int i = 0; i < m; i++)
        {
            s.Merge(a[i][0], a[i][1]);
        }
        return s.ReturnCount();
    }
    void TestFriends()
    {
        const int n = 5;
        const int m = 3;
        int a[m][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 } };
        cout<<"朋友圈的个数？--》"<<Friends(m, n,a)<<endl;
    }

下一期还会介绍并查集在求解图的最小连通图算法中的应用，请多多关注。

[20161203111044242]: /images/20220714/91d4d668182646729e9d65a84fb942c4.png
[20161203113813918]: /images/20220714/24619e431c0d4c89a9d503142acd4365.png