likeJ

并查集

# Hash 和 Hash 表(1) # kmp 算法(1) # LCA（最近公共祖先）(1) # 二分(2) # 广搜bfs(16) # 树形dp(3) # 深搜dfs(8) # 贪心(4) # 递推(6) 1024程序员节(1) c++杂题(3) hash(4) STL(1) ST表(1) 二分图(5) 信息奥赛一本通——高效进阶(13) 动规dp(17) 单调栈(6) 单调队列(8) 图论(1) 快速幂(2) 拓扑排序(6) 数论(2) 最小生成树(3) 最短路径(15) 未归档(4) 树状数组(4) 状态压缩(7) 矩阵乘法(2) 离散化(4) 线段树(5) 赛后分析(88) 邻接表(2)

/ 注册

全部文章 / 并查集（共9篇）

P1536 村村通（并查集）

村村通题目传送门题目描述某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？输入格式每个输入文件包含若干组测...

2021-03-26

0 559

P1111 修复公路（并查集）

修复公路题目背景 A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在...

2021-03-26

0 658

P2078 朋友（并查集）

朋友题目背景小明在A公司工作，小红在B公司工作。题目描述这两个公司的员工有一个特点：一个公司的员工都是同性。 A公司有N名员工，其中有P对朋友关系。B公司有M名员工，其中有Q对朋友关系。朋友的朋友一定还是朋友。每对朋友关系用两个整数(Xi,Yi)组成，表示朋友的编号分别为Xi，Yi...

2021-03-26

0 597

P1551 亲戚（并查集）

亲戚题目背景若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。题目描述规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式第一行：三...

2021-03-26

0 596

P3367 【模板】并查集（并查集）

【模板】并查集题目传送门题目描述如题，现在有一个并查集，你需要完成合并和查询操作。输入格式第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。接下来M 行，每行包含三个整数Zi,Xi,Yi。当Zi=1 时，将Xi与Yi所在的集合合并。当Zi=2 时，输出Xi与...

2021-03-26

0 573

旅行（并查集）

旅行 Description Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点（编号为1,2,3,…,N），这些景点被M条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri...

2021-03-26

0 380

矩形（并查集）

矩形 Description 在一个平面上有n个矩形。每个矩形的边都平行于坐标轴并且都具有值为整数的顶点。我们用如下的方式来定义块。每一个矩形都是一个块。如果两个不同的矩形有公共线段，那么它们就组成了一个新的块来覆盖它们原来的两个块。例子：在图1中的矩形组成了两个不同的块。 Inpu...

2021-03-26

0 637

家谱（并查集）

家谱 Description 现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。 Input 输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name 的形式描写一组父子关系中的父亲的名字，用+n...

2021-03-26

0 726

最短网络（并查集）

最短网络 Description 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间...

2021-03-26

0 496