关键词：
Rt
题目背景
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入输出格式
输入格式：
第1行两个正整数N，M
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。
输出格式：
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
输入：
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出：
5
分析：
首先读题发现是一道并查集的 水 题，先对t从小到大排序，然后挨个合并，但怎么判断合并全了？
这时我们需要一个很巧妙的方法
可以建一个val[ ]=1；然后集合合并时val相加
详见代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int val[1000010];
//并查集
struct b
{
int par[1000100];
inline void ih(){for(int i=1;i<=n;++i) {par[i]=i;val[i]=1;}}
inline int f (int x){return par[x]=(par[x]==x)?x:f(par[x]);}
inline int u (int x,int y)
{
val[f(x)]+=val[f(y)];//对祖先的val操作
par[f(y)]=f(x);
}
inline int get_val (int x)
{
return val[f(x)];
}
}s;
struct data
{
int x,y,t;
friend bool operator < (data a,data b)
{
return a.t<b.t;
}
}a[10100000];
int sum=2,ans;
bool flag=0;
int main()
{
freopen("in","r",stdin);
scanf("%d%d",&n,&m);
scanf("%d%d%d",&a[0].x,&a[0].y,&a[0].t);
for(int i=1;i<m;++i)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
}
sort(a,a+m);
s.ih();
for(int i=0;i<m;++i)
{
if(s.f(a[i].x)!=s.f(a[i].y))
{
s.u(a[i].x,a[i].y);
ans=a[i].t;
if(s.get_val(a[i].x)==n)
{
printf("%d",ans);
flag=1;
break;
}
}
}
if(flag==0)
{
printf("-1");
}
}
View Code
并查集的一般操作③
RT 题目描述 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是： 我朋友的朋友是我的朋友； 我敌人的敌人也是我的朋友。 两个强盗是同... 查看详情
数据结构--并查集的原理及实现(代码片段)
一，并查集的介绍 并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。而在某次合并之后，有一种... 查看详情
并查集的一般操作②
RT 题目描述 明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云... 查看详情
并查集的基本操作和用法(代码片段)
并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情
并查集的基本操作和用法(代码片段)
并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情
并查集的删除操作(代码片段)
...一开始所有信件都是单独的文件夹。其实就是一个简单的并查集删除的操作，当删除时就创建新的结点来代替它,要注意的是数组的范围，虽然信件只有10的5次方，但是操作有10的6次方，因为删除时还得 查看详情
❤️数据结构入门❤️（2-5）-并查集
文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情
hdu2473junk-mailfilter(并查集的删除操作)
ProblemDescriptionRecognizingjunkmailsisatoughtask.Themethodusedhereconsistsoftwosteps:1)Extractthecommoncharacteristicsfromtheincomingemail.2)Useafiltermatchingthesetofcommoncharacteristicsextractedt 查看详情
并查集的简介
最近做题用到了并查集索性就把自己所掌握的相关知识总结一下。 并查集(union-findsets),CLRS上称为disjoint-set,是一组不相交的动态集合S1,S2,....Sk。它能够实现较快的合并和判断元素所在集合的操作，应用比较广泛，如其求... 查看详情
hdu2473junk-mailfilter(并查集的删除操作)
...来。。如今又做了做，还是没做出来。。、、这题涉及到并查集的删除操作。想到了设一个虚节点，可是我把虚节点设为了要删除的点的父节点。一直是栈溢出，目測是无限递归了。看了看别人的做法。原来仅仅要建一个映射就... 查看详情
并查集
并查集1.并查集是什么并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。查询元素a和元素b是否属于同一组。合并元素a和元... 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
朋友(并查集的删除操作可看作是插入操作的逆序)
小z被选为他们村的村长，现在小z调查他们村上的关系。如果村民a和村民b是朋友，村民b和村民c是朋友，那么村民a和村民c也是朋友。那么村上的村民就会形成一个“朋友”团队，现在小z想知道他们村长有多少个这样的团队。同... 查看详情
restructuringcompany和almostunion-find并查集的区间合并与并查集的删除
RestructuringCompany Eventhemostsuccessfulcompanycangothroughacrisisperiodwhenyouhavetomakeaharddecision—torestructure,discardandmergedepartments,fireemployeesanddootherunpleasantstuff.Let‘sconsi 查看详情
数据结构-树并查集的定义及其操作(代码片段)
...化3查找操作4并操作1数据结构定义#defineMAX50intUFSets[MAX];//并查集2初始化//参数：并查集SvoidInit(intS[])inti;for(i=0;i<MAX;i++)S[i]=-1;【注】根结点可用来保存该子集合的元素个数（负数表示）。3查找操作寻找包... 查看详情
并查集的优化及应用
2018-05-0115:13:08并查集是一个时空复杂度非常优越的数据结构，并且通过优化后其复杂度为<O(1)，O(n)>。并查集的优化主要有两个方面：路径压缩按rank来合并路径压缩：按rank合并：publicclassUnionFindSetprivateint[]parent;privateint[]rank;p... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情