文档章节

并查集应用入门

laomd
 laomd
发布于 2017/03/21 20:56
字数 886
阅读 6
收藏 0

朋友圈问题:

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

输入:

输入包括多个测试样例,每个测试样例的第一行为正整数n和m,1 <= n,m <= 100000。接下来有m行,每行分别为连个人的编号f,t(1 <= f, t <= n),表示f和t是好友。当n为0时输入结束。

输出:

一行,这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
粉丝 0
博文 31
码字总数 12000
作品 0
广州
私信 提问
《机器学习》笔记-模型评估与选择(2)

机器学习算法全栈工程师 一个用心的公众号 长按,识别,加关注 进群,学习,得帮助 你的关注,我们的热度, 我们一定给你学习最大的帮助

机器学习算法全栈工程师
2018/01/29
0
0
Spring经典视频教程大集合

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

IT小白白
2012/10/08
0
0
完整的权限管理系统 - LaySSH

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

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

本文将使用pytorch框架训练一个四层卷积神经网络,用以识别四位数字字母区分大小的验证码。 1. 引言 去年四六级查分时候我把准考证号忘了,准考证一时也找不到,最后是靠试准考证号试出来的,...

icetong_k
05/12
0
0
算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy
2017/10/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

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

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

小小编辑
41分钟前
419
9
解决Structure needs cleaning

简介 今天在同步文件的时候有一个目录突然报错 Structure needs cleaning 百度了一下发现使用xfs_repair可以解决 操作 因为我做的是raid5 ,可能是昨天我重启了机器的缘故,所以我要做的是先...

bboysoulcn
今天
6
0
Dubbo服务暴露与注册

前面的文章中,我们讲解了Dubbo是如何进行配置的属性的初始化的,并且讲到,Dubbo最终会将所有的属性参数都封装为一个URL对象,从而以这个URL对象为基准传递参数。本文则主要讲解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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部