java并查集找朋友圈_图—并查集（解决朋友圈问题）
图也是一种 非线性结构，是由多个顶点组成的关系集合组成的一种数据结构。图可以分为两种，无向图和有向图。
★图的定义:
★典型问题：
利用图能够解决很多问题，这里有一个较为典型的问题，假如已知有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个朋友圈。
★解题思路：
首先，先介绍一个概念：并查集。并查集就是将N个不同元素分成一组不想交的集合，开始时，每个元素就是一个集合，然后按规律将两个集合进行合并。具体的做法如下：
设定一个有N个元素的数组，将每个元素对应的位置都置为-1，即就是先让其没有相交，然后根据题目中给出的朋友关系，将根节点元素对应的位置减1，将与根节点是好友的元素对应的位置更改为根节点元素，按照这样的方式，将所有的关系都进行对应，最后数组中如果是负数，所对应的元素就是根节点。
★具体代码：#pragma once
#include
//实现图 ——并查集
/*
主要功能：给定一个范围，能够确定朋友圈的个数
*/
class UnionFindSet
{
public:
UnionFindSet(size_t size) //构造函数
:_n(size)
, _set(new int[size])
{
for (int i = 0; i
{
_set[i] = -1;
}
}
void Union(int root1, int root2) //结合两个根节点
{
assert(_set[root1]
assert(_set[root2]
_set[root1] += _set[root2];
_set[root2] = root1;
}
size_t FindRoot(int child)
{
if (_set[child]
{
return child;
}
int num = _set[child];
while (num >= 0)
{
num = _set[num];
}
return num;
}
void print()
{
int root = 0;
for (int i = 0; i
{
if (_set[i]
{
root++;
}
}
cout <
}
protected:
int* _set; //数组指针
size_t _n; //给定范围数据的个数
};
void Test()
{
UnionFindSet ht(10);
ht.Union(0, 6);
ht.Union(0, 7);
ht.Union(0, 8);
ht.Union(1, 4);
ht.Union(1, 9);
ht.Union(2, 3);
ht.Union(2, 5);
ht.print();
}
总结
以上是生活随笔为你收集整理的java并查集找朋友圈_图—并查集（解决朋友圈问题）的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： Linux 监控命令之 vmstat
- 下一篇： 更改Web应用地址栏显示的图标