ccf 201703-4 地铁修建（95）（并查集）

ccf 201703-4 地铁修建（95）

　　使用并查集，将路径按照耗时升序排列，依次加入路径，直到1和n连通，这时加入的最后一条路径，就是所需要修建的时间最长的路径。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100000+10;
const int maxm = 200000+10;
long n,m;
struct node{
    long ci,cj,cij;
}Edge[maxm];
long pro[maxn];
bool compare(node a,node b)
{
    return a.cij<=b.cij;
}

long find(long a)
{
    if(pro[a] == a)
    {
        return pro[a];
    }
    pro[a] = find(pro[a]);//进行路径压缩 
    return pro[a]; 
}

void unionIJ(long a,long b)
{
    long pa = find(a);//找到a的祖先，并且在查找的过程中进行路径压缩
    long pb = find(b); 
    pro[pb] = pa;
}
int main()
{
    cin>>n>>m;
    for(long i=0;i<m;i++)
    {
        cin>>Edge[i].ci>>Edge[i].cj>>Edge[i].cij;
    }
    sort(Edge,Edge+m,compare);
    //从最短的路开始，建立并查集
    for(long i=1;i<=n;i++)
    {
        pro[i] = i;
    }
    for(long i=0;i<m;i++)
    {
        ///将ci和cj的祖先合并
        unionIJ(Edge[i].ci,Edge[i].cj); 
        //判断1和n是否联通
        if(find(1) == find(n))
        {
            cout<<Edge[i].cij<<endl;
            break; 
         } 
     } 
    return 0;
}