你到底有多少个朋友圈?

淡淡的烟草味﹌ 2022-07-14 05:18 244阅读 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属于同一个朋友圈.结果为两个朋友圈.

如何去分析这道面试题呢？这就用到**并查集**这种数据结构.

**并查集>**

将N个不同的元素分成一组不相交的集合，开始时，每个元素就是一个集合，然后按规律将两个集合进行合并,在合并的过程中要不断的查找这个元素属于哪个集合.

![Center][]

在统计朋友圈的数量的时候只需要统计负数的个数即可.

#pragma once
    
    class UnionSet
    {
    public:
    	UnionSet(int size)
    		:_size(size+1)
    	{
    		_a=new int[size+1];
    		memset(_a,-1,sizeof(int)*(size+1));
    	}
    	~UnionSet()
    	{
    		delete[]_a;
    		_size=0;
    	}
    	void Merge(int x1,int x2)
    	{
    		int root1=_GetRoot(x1);
    		int root2=_GetRoot(x2);
    		if(root1 != root2)
    		{
    			_a[root1] += _a[root2];
    			_a[root2] = root1;
    		}
    	}
    	int CountFriends()
    	{
    		int count=0;
    		for(int i=0;i<_size;++i)
    		{
    			if(_a[i] < 0)
    			{
    				count++;
    			}
    		}
    		return count-1;
    	}
    protected:
    	int _GetRoot(int index)
    	{
    		int root=index;
    		while(_a[root] >= 0)
    		{
    			root=_a[root];
    		}
    		return root;
    	}
    protected:
    	int *_a;
    	int _size;
    };
    
    void testUnionSet()
    {
    	const int n=5;
    	const int m=4;
    	int a[m][2]={
       {1,2},{2,3},{4,5},{1,3}};
    	UnionSet unionset(n);
    	for(int i=0;i<m;++i)
    	{
    		unionset.Merge(a[i][0],a[i][1]);
    	}
    	cout<<"Friends:"<<unionset.CountFriends()<<endl;
    }

在这里就分享结束啦~~~

[Center]: /images/20220714/1a14a3be332e4a61b95e2c430c777d8b.png