动态连通性问题——算法union-find
2024-09-05 05:44:00
问题定义：问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p,q可以被理解为"p和q是相连的"。我们假设“相连”是一种对等的关系。
这也意味着它具有：
1.自反性：p和q是相连的；
2.对称性：如果p和q是相连的，那么q和p也是相连的；
3.传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的；
对等关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时他们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对（两个整数均来自于同一个等价类中）。换句话说，当程序从输入中读取了整数对p q时，如果一直的所有整数写入到输出中。如果已知的数据可以说明p和q是相连的。那么程序应该忽略p q这对整数并继续处理输入中的下一对整数。为了达到所期望的效果，我们需要设计一个数据结构来保存程序一直的所有整数对的足够多的信息，并用他们来判断一对新对象是否相连。我们将这个问题通俗地叫做动态连通性问题。在网络，变量名等价性和数学集合等问题中有应用
最新文章
- android异常: java.net.ConnectException: localhost/127.0.0.1:8080 - Connection refused
- 屏幕适配1（Android 增强版百分比布局库 为了适配而扩展）
- C语言 homework (3)
- [WinAPI] API 2 [MessageBox API][消息框API]
- Material Design UI Widgets
- DS实验题 击鼓传花
- [SQL]合并字符串
- css required,focus,valid和invalid介绍
- java.io.File类
- （C语言）char类型与int类型相加
- nopCommerce 3.9 大波浪系列 之 微信公众平台登录插件
- 小白的python之路11/3内存 进程 二进制软件包 rpm yum
- post文件下载
- pandas数据的分组与分列
- MongoDB统计文档(Document)的数组(Array)中的各个元素出现的次数
- 4-13 object类，继承和派生（ super） ,钻石继承方法
- 3.1.1 Spring 简介
- python：利用smtplib模块发送邮件
- Lucene原理一
- Phonegap 工程项目介绍