## 并查集应用入门 原

laomd

假设已知有n个人和m对好友关系，如果两个人是直接或间接的好友关系（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

5 3

1 2

2 3

4 5

3 3

1 2

1 3

2 3

0

2

1

开一个一维数组，下标i代表编号，值代表朋友的编号。最后遍历时候，如果friends[i] != i，则说明编号i的人和其他人有朋友关系，n--。

代码如下：

``````class union_find {
public:
union_find(unsigned numOfPeople);
~union_find();

void combine(unsigned persona, unsigned personb);
unsigned get_cycle() const;

private:
int *people = nullptr;
unsigned num;

unsigned find(unsigned person) const;
void unite(unsigned cycleA, unsigned cycleB);
};``````
``````union_find::union_find(unsigned n) : num(n), people(new int[n + 1]) {
for (unsigned i = 1; i <= count; ++i) {
people[i] = i;
}
}

union_find::~union_find() {
delete people;
nodes = nullptr;
}

unsigned union_find::find(unsigned person) const {
return people[person];
}

void union_find::combine(unsigned persona, unsigned personb) {
unite(find(persona), find(personb));
}

void union_find::unite(unsigned cycleA, unsigned cycleB) {
if (cycleA != cycleB)
{
for (int i = 1; i <= count; i++) {
if (people[i] == cycleB)
people[i] = cycleA;
}

}
}

unsigned union_find::get_cycle() const {
int n = num;
for (int i = 1; i <= num; i++) {
if (people[i] != i)
n--;
}
return n;
}
``````

思路一的缺点在于同一个朋友圈的人没有建立起联系，因而需要对数组进行整个迭代。思路二改进了这一点，在朋友圈里面找一个人当领头人，通过他可以找到朋友圈里面的所有人。

``````class union_find {

struct person {
unsigned cycle;//领头人的编号
unsigned size = 0;//朋友圈的人数，只有领头人才设置
unsigned next = 0;//下一个朋友的编号，如果为0则说明没有
};

public:
union_find(unsigned numOfPeople);
~union_find();

void combine(unsigned persona, unsigned personb);
unsigned get_cycle() const;

private:
person *people = nullptr;
unsigned num;

unsigned find(unsigned person) const;
void unite(unsigned cycleA, unsigned cycleB);
};``````
``````union_find::union_find(unsigned n) : num(n), people(new person[n + 1]) {
for(unsigned i = 1; i <= num; ++i) {
people[i].cycle = i;
people[i].next = 0;
}
}

union_find::~union_find() {
delete people;
people = nullptr;
}

unsigned union_find::find(unsigned person) const {
return people[person].cycle;//找到领头人
}

void union_find::combine(unsigned persona, unsigned personb) {
unite(find(persona), find(personb));
//如果两个人是朋友，那他们所属的两个朋友圈实际上就是一个朋友圈
//把其中一个朋友圈所有人的领头人换掉即可
}

void union_find::unite(unsigned cycleA, unsigned cycleB) {
if (cycleA != cycleB) {
if(people[cycleA].size < people[cycleB].size)//把小的朋友圈换掉
unite(cycleB, cycleA);

unsigned k = cycleB;
while(people[k].next != 0) {
people[k].cycle = cycleA;//换掉领头人
k = people[k].next;
}
//此时k指向朋友圈B的最后一个人
people[k].cycle = cycleA;

//朋友圈B插入到A中
people[k].next = people[cycleA].next;
people[cycleA].next = cycleB;

people[cycleA].size += people[people[cycleA].next].size;
people[people[cycleA].next].size = 0;

num--;
}
}

unsigned union_find::get_cycle() const {
return num;
}``````

``````class union_find
{
struct person
{
unsigned parent;
};
public:
union_find(unsigned numOfPeople);
~union_find();

void combine(unsigned persona, unsigned personb);

unsigned get_cycle() const;

private:
person *people = nullptr;
unsigned num;

unsigned find(unsigned person) const;
void unite(unsigned cycleA, unsigned cycleB);
};``````
``````        union_find::union_find(unsigned n) : num(n), people(new person[n + 1])
{
for(unsigned i = 1; i <= num; ++i) {
people[i].parent = 0;
}
}
union_find::~union_find()
{
delete people;
people = nullptr;
}
unsigned union_find::find(unsigned person) const
{
while(people[person].parent) {
person = people[person].parent;
}
return person;
}
void union_find::combine(unsigned persona, unsigned personb)
{
unite(find(persona), find(personb));
}
void union_find::unite(unsigned cycleA, unsigned cycleB)
{
if (cycleA != cycleB)
{
people[cycleB].parent = cycleA;

num--;
}
}
unsigned union_find::get_cycle() const
{
return num;
}``````

### laomd

《机器学习》笔记-模型评估与选择（2）

2018/01/29
0
0
Spring经典视频教程大集合

Spring经典视频教程大集合 Spring是一个开源框架，它由RodJohnson创建。它是为了解决企业应用开发的复杂性而创建的。Spring使用基本的JavaBean来完成以前只可能由EJB完成的事情。然而，Sprin...

IT小白白
2012/10/08
0
0

LaySSH是一款完全开源免费的开发框架，基于LayUI+SpringMVC+Spring+Hibernate+Mysql搭建而成，内置代码生成器，能够快速生成增删改查代码，节省开发时间，快速构建企业级的web应用系统。 该框...

herun
2018/02/02
0
0
pytorch入门实战之验证码识别

icetong_k
05/12
0
0

rainchxy
2017/10/23
0
0

OSChina 周一乱弹 —— 满周岁就去挣钱！

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @ tom_tdhzz：一直期待了很久，这是第二次来圆明园，也是特意来这里，只是才发现只有历史现实不在了。#今日歌曲推荐# 分享王晰的单曲《南屏晚...

41分钟前
419
9

bboysoulcn

6
0
Dubbo服务暴露与注册

4
0
Leetcode PHP题解--D88 696. Count Binary Substrings

D88 696. Count Binary Substrings 题目链接 696. Count Binary Substrings 题目分析 给定一个01字符串，返回仅用连续的0和1串所能组成的二进制字符串个数。 例如，00110011，就包含0011，0...

skys215

4
0

package com.atguigu.util;import java.sql.Connection;import java.sql.SQLException;import java.util.Properties;import javax.sql.DataSource;import com.alibaba.druid......

architect刘源源

103
0