P1111 修复公路 题解

这道题就是并查集的练手好题QAQ

如果对并查集不熟悉的同学可以做一下这道题

来看一下题目：

给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

我们可以将这N个村庄看成N个点，其中M是我们要合并的次数。

很明显，修路时间t越早的就要越早合并，所以要先排序！(样例中都能看出来)

排序后，按照时间逐个合并，如果合并过程中道路连通，那么输出时间;否则输出-1

但是如果按时间排序，x,y也要跟着动，怎么办呢？用结构体！结构体不会的可以自行离开了

如何判断当前N个点有没有在一个集合内呢？

我们设fa[i]是第i个人的祖先，初始化fa[i]=i，各自是各自的祖先

当合并一次之后，我们扫一遍fa数组，统计fa[i]=i的个数：

1. 如果只有1个fa[i]=i，就说明所有的全部联通了（因为只有1个人是自己的祖先，别的人都跟着他）
2. 如果不止1个，就说明当前没有全部联通（因为两个人互相没有关系），需要继续合并。

时间复杂度可能会有点高，但足够通过本题了。

上代码：

#include
using namespace std;
int fa[1000+10],n,m;
struct node
{
 int x,y,t;
}a[100000+10];//结构体大法好！
bool cmp(node fir,node sec)
{
 return fir.t=2），输出-1
 return 0;//愉快的结束主程序
}