洛谷p1111 修复公路 最小生成树

题目背景

AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

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

输入格式

第11行两个正整数N,MN,M

下面MM行，每行33个正整数x, y, tx,y,t，告诉你这条公路连着x,yx,y两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1−1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

N le 1000,M le 100000N≤1000,M≤100000

x le N,y le N,t le 100000x≤N,y≤N,t≤100000

//对于100%的数据，N<=10000，M<=200000。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;
int father[maxn];
int num[maxn];
void init()
{
    for(int i=1;i<maxn;++i)
    {
        father[i]=i;
        num[i]=1;
    }
}
int find(int x)
{
    if(x==father[x])
    {
        return x;
    }
    int temp=x;
    while(temp!=father[temp])
    {
        temp=father[temp];    
    }
    int ans = temp;
    int a=x;
    while(a!=father[a])
    {
        father[a]=ans;
        a=father[a];
    }
    return ans;
}
void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        father[p]=q;
        //num[q]+=num[p];
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        num[q]+=num[p];        
        return true;
    }
    else return false;
}

struct node{
    int from;
    int to;
    int time;
}arr[200005];

bool cmp(node a,node b)
{
    return a.time<b.time;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        init(); 
        for(int i=1;i<=m;++i)
        {
            cin>>arr[i].from>>arr[i].to>>arr[i].time;
        }
        sort(arr+1,arr+m+1,cmp);
        int flag=1;
        for(int i=1;i<=m;++i)
        {
//            for(int i=1;i<=n;++i)
//            {
//                cout<<num[i];
//            }
//            cout<<endl;
            int x=arr[i].from;
            int y=arr[i].to;
            if(judge(x,y))
            {
                merge(x,y);
                if(num[find(y)]==n)
                {
                    cout<<arr[i].time<<endl;
                    flag=0;
                    break;
                }
            }
        }
        if(flag)
        {
            cout<<"-1"<<endl;
        }
    }
    return 0;
}