精选文章 并查集的应用

并查集的应用

作者:2013221 时间: 2016-06-30 09:54:01
2013221 2016-06-30 09:54:01
  • 定义

 并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

  • 应用

 若某个朋友圈过于庞大,要判断两个人是否是在一个朋友圈,确实还很不容易,给出某个朋友关系图,求任意给出的两个人是否在一个朋友圈。 规定:x和y是朋友y和z是朋友,那么x和z在一个朋友圈。如果x,y是朋友,那么x的朋友都与y的在一个朋友圈,y的朋友也都与x在一个朋友圈

如下图:

  并查集的应用1

代码:

//找朋友圈个数
//找父亲节点
int FindRoot(int child1, int *_set)
{
	int root = child1;
	while (_set[root] >= 0)
	{
		root = _set[root];
	}
	return root;
}
//合并
void Union(int root1, int root2, int *&_set)
{
	_set[root1] += _set[root2];
	_set[root2] = root1;
}
int Friend(int n, int m, int r[][2])//n为人数,m为组数,r为关系
{
	assert(n > 0);
	assert(m > 0);
	assert(r);
	int *_set = new int[n];
	for (int i = 0; i < n+1; i++)
	{
		_set[i] = -1;
	}
	for (int i = 0; i < m; i++)
	{
		int root1 = FindRoot(r[i][0],_set);
		int root2 = FindRoot(r[i][1],_set);
		if ((_set[root1] == -1 && _set[root2] == -1) || root1 != root2)
		{
			Union(root1, root2, _set);
		}
	}
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		if (_set[i] < 0)
		{
			count++;
		}
	}
	return count;

}
//主函数
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
#include
#include"UnionFindSet.h"
int main()
{
	int r[][2] = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 } };
	cout << Friend(6, 4, r) << endl;
	system("pause");
	return 0;
}
勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:keepalived配置文件说明

下一篇:Linux常用的shell命令汇总

您可能感兴趣

  • SIP语音环境中十大经典问题及解决办法

    在VOIP的环境中,特别是基于SIP通信的环境中,我们经常会遇到一些非常常见的问题,例如,单通,30秒就断线,注册问题,回声等。这些问题事实上都有非常直接的排查方式和解决办法,用户可以按照一定的排查方式,工具非常高效地解决这些问题。但是,因为读者技术水平参差不齐,网络上的很多技术也不完整。笔者今天系统归纳了这些问题。根据一些用户的使用环境和用户经常遇到一些问题,我们列举了以下十个在SIP呼叫...

  • 实验室作业之英文文本聚类

    给出已经分好的英文数据集,数据集中没有重复的单词,进行文本聚类 聚类就是先把英文单词转化为向量,根据要聚成多少类,随机选择点,用欧氏距离或者余弦距离进行计算,把随机选择的中心点附近的点跟他归为一类,所以要先计算tdidf的值, 关于pycharm中kmeans包中的函数介绍 n_clusters: 簇的个数,即你想聚成几类 init: 初始簇中心的获取方法 n_init: 获取初始簇中心的更...

  • HIDL详解-Android10.0 HwBinder通信原理(二)

    摘要:本节主要来讲解Android10.0 HIDL相关知识 阅读本文大约需要花费18分钟。 文章首发微信公众号:IngresGe 专注于Android系统级源码分析,Android的平台设计,欢迎关注我,谢谢! [Android取经之路] 的源码都基于Android-Q(10.0) 进行分析 [Android取经之路] 系列文章: 《系统启动篇》 Android系统架构 Android是怎...

  • SpringMVC框架的入门学习01

    SpringMVC的基本概念 关于三层架构和MVC 三层架构 我们的开发架构一般都是基于两种形式,一种是 C/S 架构,也就是客户端/服务器,另一种是 B/S 架构,也就是浏览器服务器。在 JavaEE 开发中,几乎全都是基于 B/S架构的开发。那么在 B/S架构中,系统标准的三层架构包括:表现层、业务层、持久层。三层架构在我们的实际开发中使用的非常多,所以很多案例也都是基于三层架构设计的。...

  • kubespray部署k8s version 1.0

    一、部署原理 基于vagrant和virtualbox,通过kubespray项目,控制ansible,部署高可用的k8s集群。 二、部署环境 1.部署拓扑 2.部署软硬件 硬件: 物理机 CPU:Double CPU,14 core,2 threads per core,CPU Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GHz 内存:64G 软件: Cent...

  • .NET Core:通过Web API进行微服务交互

    目录 介绍 命名协议 MicroCommerce应用程序结构 MicroCommerce应用开发 1.接口项目,微服务接口和模型类 2. ProductCatalog项目 3. ShoppingCart项目 4. ActivityLogger项目 5. WebUI项目,用户界面 6.关于通用功能的几句话 应用测试 结论 缺点 下载源代码26.3 KB 介绍 几乎所有在.NET Core中使用...

  • MemCache详细解读

    本节内容主要关于mencache的工作原理,memcache的应用场景及其应用实例配置,memcache安装部署。 一、Memcached工作原理 1.服务端缓存实现 (1)memcached特性 分布式: 实例和缓存在逻辑上是分离的 普通缓存 Memcached缓存 特 性 缓存与特定的应用实例绑定,每个应用实例只能访问特定的缓存 实例独立于各个应用服务器实例运行,每应用实例可以访问任意缓...

  • 2020B证(安全员)考试及B证(安全员)模拟考试题库

    题库来源:安全生产模拟考试一点通公众号小程序 2020B证(安全员)考试及B证(安全员)模拟考试题库,包含B证(安全员)考试答案解析及B证(安全员)模拟考试题库练习。由安全生产模拟考试一点通公众号结合国家B证(安全员)考试最新大纲及B证(安全员)考试真题出具,有助于B证(安全员)考试软件考前练习。 1、【单选题】多台挖掘机在同一作用面机械开挖,挖掘机间距应大于( )。( B ) A、5m B...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
51CTO

51CTO

51CTO是一家综合的IT技术用户服务平台,立足满足用户多维度需求,为技术用户成长赋能。2005年成立至今,拥有专业主流技术媒体51CTO企业信息化媒体CIOAge中国最大的IT在线教育平台51CTO学院。