精选文章 并查集的应用

并查集的应用

作者:2013221 时间: 2021-02-05 09:35:42
2013221 2021-02-05 09:35:42
【摘要】定义 并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。应用 若某个朋友圈过于庞大,要判断两个人是否是在一个朋友圈,确实还很不容易,给出某个朋友关系图,求任意给出的两个人是否在一个朋友圈。 规定:x和y是朋友,y和z是朋友,那么x和z在一个朋友圈。如果x,y是朋友,那么x的朋友都与y的在一个朋友圈,y的朋友也都与x在一...
  • 定义

 并查集是一种树型的数据结构,用于处理一些不相交集合(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占位
分享文章到微博
分享文章到朋友圈

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

下一篇:由于iptables导致nginx的499

您可能感兴趣

  • CTI的典型应用之三

    CTI的典型应用之三◆ 电话语音卡 黄至周   电话语音卡,确切地说,应称为“电脑与电话语音处理卡”,作为公共电话网与电脑的接口设备,近年来在中国通讯市场中异军突起,正日益成为发展最快,应用最广的通讯产品之一。短短几年中,其应用领域从最初的“证券委托”,逐步拓展到邮电通讯、信息服务、办公自动化、金融、公安、医疗、商业、娱乐、交通运输、工业生产及社会生活等各个方面,并且还将以更快的速度继续发...

  • 基于MySQL的高性能数据库应用开发

    在数据库的应用开发中,常常会遇到性能和代价的之间矛盾。以作者在开发股市行情查询和交易系统中遇到的问题为例,要在实时记录1000多只股票每分钟更新一次的行情数据的同时,响应大量并发用户的数据查询请求。考虑到性价比和易维护性,系统又要求在基于PC服务器,Windows NT平台的软硬件环境下实现。开始,我们采用了MS SQL Server 6.5 作为数据库系统,用Visual C++ 6.0开...

  • 关于包(Package)应用规范的说明

    一、 dataBase端开发介绍:package分为两个部分:1、package head,2、package body。前者为包头的定义,后者为过程及方法的实体。只要包头定义中描述足够详细,可以隐藏包体的细节。举例如下:package head pkg_topnetis--user define data type—--用户自定义数据类型--    --user define proced...

  • VB中子分类技术的应用

    子分类技术的原理:要先取得原先Window Procedure所在的地址,将之记录起来,接着设定所有的消息都先转到我们所写的消息处理过程上来,我们过滤传过来的消息,寻找特定的消息进行处理,其余的送回系统,由系统决定如何处理。等到我们不需要再处理这些特定的消息时,便取消消息的截取,即中止子分类过程。它一般需要三个过程:开始截取,消息处理,中止截取.   程序需要一个模块,在模块中声明如下:  ...

  • php编写大型网站问题集

    php编写大型网站问题集  PHP以其易用性得到迅速的推广,但易用并不是说就能用好它,实际上许多程序员用它很容易的立一个个WEB应用系统,但又有多少人仔细的考虑过他们的代码,是否容易维护、是否足够健壮、否效率足够高、是否足够安全,当PHP用于建立大型网站时这些就成为很关键的因素。下面我们从较轻微的问题开始讨论,直至一些致命的错误。共分三部分。 第一部分、较轻微的错误 一、Printf(),...

  • 利用ASP开发Web应用

    利用ASP开发Web应用 通常情况下,用户通过浏览器看到的网页大多是静态的,而随着Web应用的发展,用户 希望能够看到根据要求而动态生成的主页,例如响应用户查询数据库的要求、生成报表等。 根据用户请求生成动态主页的传统方法有CGI、ISAPI等。CGI是根据浏览器端的http请 求激活响应进程,每一个请求对应一个进程。当同时有很多请求时,程序挤占系统资源,造 成效率低下;ISAPI针对这...

  • PowerBuilder应用开发系列讲座(1)

    PowerBuilder应用开发系列讲座(1)张健姿   在数据库中,所谓事务是指一组逻辑操作单元,使数据从一种状态变换到另一种状态。为确保数据库中数据的一致性,数据的操纵应当是离散的成组的逻辑单元:当它全部完成时,数据的一致性可以保持,而当这个单元中的一部分操作失败,整个事务应全部视为错误,所有从起始点以后的操作应全部回退到开始状态。    对事务的操作是这样进行的:先定义开始一个事务,然...

  • 控件在应用程序的应用

    在窗口中添加控件  一个成功的应用程序离不开漂亮的界面。本章主要谈谈Windows内置的控件在应用程序中的应用,包括如何声明变量并把它们和控件相关联;如何在控件和变量的值之间保持同步;如何使用控件对象ID来检索控件对象,从而操纵控件,以及如何把控件作为窗口来处理;还有如何指定应用程序窗口中控件选项卡的顺序,从而控制用户在窗口中切换应用程序的顺序。小生以前从来没有写过什么文章,在此借此机会希望...

51CTO

51CTO

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

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

免费套餐,马上领取!
并查集的应用介绍:华为云为您免费提供并查集的应用在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多并查集的应用的相关内容。| 移动地址: 并查集的应用 | 写博客