codevs 1638_洛谷 1111_修复公路_并查集

发布于 2019-04-29  892 次阅读


题目大意

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


思路

就是一个并查集,然后将时间从小到大排序,每次取最小的合并,如果可以合并就判断减少一个集合,最后只剩一个集合时输出时间


#include 
#include 
using namespace std;
struct arr
{
    int x,y,t;
};

arr a[1000000];
int f[1000000];

int find(int x)
{
    if (!f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}

int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int cam(arr a,arr b)
{
    return a.t
]]>